Re: [問題] usaco 2-3 Cow Pedigrees (檔名 nocows)
看板Prob_Solve (計算數學 Problem Solving)作者s213895 (鬼才)時間18年前 (2007/02/24 20:41)推噓0(0推 0噓 0→)留言0則, 0人參與討論串2/4 (看更多)
我後來有去看別人是怎麼作的
以下的程式碼不用全看完
/*
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
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
