PKU 2084 Game of Connections
http://poj.org/problem?id=2084
読む。紙に書いて考える。
珍しく動的計画法だと気づき、漸化式も立てられた。
なーんだ、気づけば簡単じゃん。
書く。
WA
んー。100を投げてみた。
負が出た。
long longにしてみた。
100は正の数だった。
提出。
WA
60あたりで負になっていた。
多倍長ェ。
足し算までならそこそこ実装できたけど、掛け算はどうだろうなぁ。
書いてみるか。
書く。
ちゃんと動くっぽい。
投げる。TLE、orz
富豪的プログラミングは許してくれませんでした。引数をconst &にする。
TLE。
関数の返り値をグローバルに置く。
通った。
基本的にstatus画面で目についた、C++でAcceptされていて、なおかつ時間が100ms切っていて、正解者数がそこそこいるような問題を解こうとしているんですが、まさかのTLE。
C++で0msのひとってどういう書き方してるんでしょうね。
stringだとやっぱり遅すぎるのでしょうかね。
string ret; string add(const string&a,const string&b){ ret.clear(); int as=a.size(),bs=b.size(); int c=0; rep(i,max(as,bs)){ int t=c; if(i<as)t+=a[as-i-1]-'0'; if(i<bs)t+=b[bs-i-1]-'0'; c=t/10; t%=10; ret+=t+'0'; } if(c)ret+=c+'0'; reverse(ALL(ret)); return ret; } string mulcret; string multc(char m,const string&a){ m-='0'; mulcret.clear(); int c=0; int as=a.size(); rep(i,as){ int t=c+m*(a[as-i-1]-'0'); c=t/10; t%=10; mulcret+=t+'0'; } if(c)mulcret+=c+'0'; reverse(ALL(mulcret)); return mulcret; } string mulret; string mult(const string&a,string b){ mulret.clear(); int as=a.size(); rep(i,as){ mulret=add(mulret,multc(a[as-i-1],b)); b+='0'; } return mulret; } string dp[101]; main(){ dp[0]="1"; for(int i=1;i<101;i++){ rep(j,i){ dp[i]=add(dp[i],mult(dp[j],dp[i-j-1])); } } int n; while(cin>>n,~n){ if(n==-1)break; cout<<dp[n]<<endl; } }