問題
http://community.topcoder.com/stat?c=problem_statement&pm=13912&rd=16523
解き方
dpの問題。
１．どのような順序で処理されるか
→petr、snukeが順番に１つずつ出していく
２．前の状態としてどのような状態があればよいか
→前に出されたカードと、それまでに重ねられたカードの数
dp[一番上のカードの数字]＝ 重ねられたカードの数の最大値とし、
毎ターンできるだけ小さな数字でカードを重ねていけば良い。
問題文中の取ることが出きる動作のうち、１枚カードを食べるというのは
要はパスしてもよいというのがわかれば上記に帰着できそうだった。
コード
class YetAnotherCardGame {
public: int maxCards(vector<int> petr, vector<int> snuke) {
int n=petr.size();
int dp[101];
memset(dp,0,sizeof(dp));
sort(all(petr));
sort(all(snuke));
FORE(i,0,n){
for(int x=100;x>=0;x--){
FORE(j,0,n)if(petr[j]>x){
dp[petr[j]]=max(dp[petr[j]],dp[x]+1);
break;
}
}
for(int x=100;x>=0;x--){
FORE(j,0,n)if(snuke[j]>x){
dp[snuke[j]]=max(dp[snuke[j]],dp[x]+1);
break;
}
}
}
return *max_element(dp,dp+101);
}
};
public: int maxCards(vector<int> petr, vector<int> snuke) {
int n=petr.size();
int dp[101];
memset(dp,0,sizeof(dp));
sort(all(petr));
sort(all(snuke));
FORE(i,0,n){
for(int x=100;x>=0;x--){
FORE(j,0,n)if(petr[j]>x){
dp[petr[j]]=max(dp[petr[j]],dp[x]+1);
break;
}
}
for(int x=100;x>=0;x--){
FORE(j,0,n)if(snuke[j]>x){
dp[snuke[j]]=max(dp[snuke[j]],dp[x]+1);
break;
}
}
}
return *max_element(dp,dp+101);
}
};
Share this
Related Posts
SRM 325 DIV1 Easy - FenceRepairing
問題
http://community.topcoder.com/stat?c=problem_statement&pm=6827&rd=10005
・穴のあいたフェンスがある。
・フェンスを修理するには、sqr- SRM 501 DIV1 Easy - FoxPlayingGame
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11284&rd=14430
・nA,nB,paramA,paramBが与えられる。
・最
- SRM 249 DIV1 Easy - TableSeating
問題
http://community.topcoder.com/stat?c=problem_statement&pm=4616&rd=7224
・テーブルが複数存在する。
・各グループ人数ごとに来店する確率が
- SRM 352 DIV1 Easy - NumberofFiboCalls
問題
http://community.topcoder.com/stat?c=problem_statement&pm=2292&rd=10709
フィボナッチ数の計算が再帰プログラムで書かれている。
このと