PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] usaco 2-3 Cow Pedigrees (檔名 nocows)

看板Prob_Solve (計算數學 Problem Solving)作者s213895 (鬼才)時間18年前 (2007/02/24 20:39)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/4 (看更多)

http://ace.delos.com/usacoprob2?a=4e4SWaoiBTO&S=nocows 這題我自己我解到一半碰到了一些問題希望各位可以指點一二以下是過程我的解題的關鍵在任何一個節點的分支度不是0就是2 在填二維DP表中我把第一維設成節點數第二維數的高度但是跑回圈的時候是先跑第二維才跑第一維 ( 節點改變的速度比高度變的速度快 ) 像這樣 int table[200][200]; int i,k; for(k=2;k<=b;k++) for(i=3;i<=a;i++) { } 其中 a和b分別是目標的節點數及高度這時回到解題關鍵任何一個節點的分支度不是0就是2 所以我就把兩顆樹分別裝到一個單獨節點的左邊及右邊形成一顆新的符合限制的樹 =>反過來說除了[1][1]之外所有符合限制的樹[i][k] 都可以由兩顆總節點樹為i-1 並至少有一顆的高度=k 넠所推得我的做法是確定左邊的高度為k-1 然後用一個迴圈跑左邊樹的節點數這時我們已經可以確定右邊樹的節點數了所以在用另一個變數去跑右邊樹的高度再把很多組(左邊樹的個數*右邊樹的個數) 加起來(排列組合) for(k=2;k<=b;k++) { temp=k-1; for(i=3;i<=a;i++) { table[i][k]=0; for(j=1;j<i;j++) for(l=1;l<=temp;l++) { table[i][k]+=table[i-j-1][temp]*table[j][l]; table[i][k]%=9901; } } } 然後左邊有的右邊也該有所以乘二又因為如果接上的左子樹=接上的右子樹在上面的乘二會造成重複所以利用他用他們高度都=k-1 以及他們的總結點數=i-1 得到要扣掉的數目是 table[(i-1)/2][k-1] 加上一些判斷條件 table[i][k]*=2; if((i-1)%2==0) { table[i][k]-=table[(i-1)/2][k-1]; table[i][k]+=9901; table[i][k]%=9901; } 把這些玩意而再加入剛剛的迴圈中就得到幾乎完整的運算過程 for(k=2;k<=b;k++) { temp=k-1; for(i=3;i<=a;i++) { table[i][k]=0; for(j=1;j<i;j++) for(l=1;l<=temp;l++) { table[i][k]+=table[i-j-1][temp]*table[j][l]; table[i][k]%=9901; } table[i][k]*=2; if((i-1)%2==0) { table[i][k]-=table[(i-1)/2][k-1]; table[i][k]+=9901; table[i][k]%=9901; } } } 再加上雜務 /* ID: s2138951 PROG: nocows LANG: C++ */ #include<stdio.h> int table[200][200]; int main() { int a,b; int i,k,j,l; int temp; int temp2; FILE *in; FILE *out; for(k=0;k<=3;k++) for(i=0;i<200;i++) table[i][k]=0; table[0][0]=1; table[1][1]=1; in=fopen("nocows.in","r"); fscanf(in,"%d %d",&a,&b); fclose(in); for(k=2;k<=b;k++) { temp=k-1; for(i=3;i<=a;i++) { table[i][k]=0; for(j=1;j<i;j++) for(l=1;l<=temp;l++) { table[i][k]+=table[i-j-1][temp]*table[j][l]; table[i][k]%=9901; } table[i][k]*=2; if((i-1)%2==0) { table[i][k]-=table[(i-1)/2][k-1]; table[i][k]+=9901; table[i][k]%=9901; } } } out=fopen("nocows.out","w"); fprintf(out,"%d\n",table[a][b]); fclose(out); return 0; 拿去跑一開始給的測資是對的系統給的一號二號測資也是對的但是在三號測資wrong answer ----- our output --------- 5024 ---- your output --------- 1208 -------------------------- ------ Data for Run 3 ------ 35 7 ---------------------------- 乎好長剩下的另po一篇 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.229.111.105