作者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