作者s213895 (鬼才)
看板Prob_Solve
标题Re: [问题] usaco 2-3 Cow Pedigrees (档名 nocows)
时间Sat Feb 24 20:41:06 2007
我後来有去看别人是怎麽作的
以下的程式码不用全看完
/*
ID: dd.ener1
PROG: nocows
LANG: C++
*/
#include <cstdio>
#include <cstring>
using namespace std;
long N,K;
long s[200][100];
void input(){
freopen("nocows.in","r",stdin);
scanf("%d%d",&N,&K);
}
long solve(){
for(long k=1;k<=K;++k){
s[1][k]=1;
for(long n=2;n<=N;++n){
s[n][k]=0;
for(long l=1;l<=n-2;++l){
s[n][k]+=s[l][k-1]*s[n-1-l][k-1];
s[n][k]%=9901;
}
}
}
}
void output(){
freopen("nocows.out","w",stdout);
printf("%d\n",(s[N][K]-s[N][K-1]+9901)%9901);
}
int main(){
input();
solve();
output();
}
很明显的
long solve(){
for(long k=1;k<=K;++k){
s[1][k]=1;
for(long n=2;n<=N;++n){
s[n][k]=0;
for(long l=1;l<=n-2;++l){
s[n][k]+=s[l][k-1]*s[n-1-l][k-1];
s[n][k]%=9901;
}
}
}
}
他的演算法看起来似乎跟我是一样的
不一样的地方在於----他两颗子数的高度都设成k-1
为此我还很疑惑得去翻了翻题目
明明就没有这条限制...
更可怕的是
printf("%d\n",(s[N][K]-s[N][K-1]+9901)%9901);
这样不是又更少了吗(疑惑)
而且这两个集合明明就没有交集...
根据这篇作者再他自己的网志
他扣掉的 是因为"因为只能知道上限"
所以"最後再扣掉差额"....
我是觉得很奇怪拉
另外
他提及
在"星牛"的"解题报告"中
是用hash作的
我觉得明明演算法我的就是对的
他的演算法似乎跟我不能两立 然後似乎就对了
请各位高手指教指教吧
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.229.111.105