作者s213895 (鬼才)
看板Prob_Solve
標題[問題] usaco 2-3 Cow Pedigrees (檔名 nocows)
時間Sat Feb 24 20:39:56 2007
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