問題
http://community.topcoder.com/stat?c=problem_statement&pm=4797&rd=7996
サイコロが５個あり、出る数字があらかじめ与えられている。与えられた数字が"354621111111111"であれば、１回目に振った数字は
"35462"である。次に5を選んでもう一回振りなおせば、"1"が出る。
１度に同時で５つのサイコロを振り直せるが、同時に振り直せる回数は３回までになる。
最後に出た数字が全て同じ数字なら５０点、すべて連続していれば４０点、４つ連続していれば３０点、３つ同じ数字かつ２つが同じ数字なら２５点、４つ同じ数字があればすべてのサイコロの目を足した数がスコアになる。
出る数字があらかじめ与えられた時、とりうる最大のスコアを求める。
解き方
ｄｐで解く問題。どうｄｐを構成するか。
まず、何回サイコロを振ったかの状態は持たなければいけない。
次に、同時にサイコロを振り直す時にどのサイコロを選ぶかを決めなければならない。
また、サイコロを振り直す時にどこまで振ったかをわからなければならない。
これより、上記の３つの状態をもつｄｐを作り、現在の状態から現在のすべてのサイコロの振り方を選んであげればよい。
コード
string rolls;
class BestYahtzeeScore {
public:
int score(vector<int> cur){
int ret=0;
int num[7]={};
FORE(i,0,5)num[cur[i]]++;
FORE(i,1,7){
if(num[i]>=5)ret=max(ret,50);
if(num[i]>=4)ret=max(ret,cur[0]+cur[1]+cur[2]+cur[3]+cur[4]);
if(num[i]>=3)FORE(j,1,7)if(i!=j&&num[j]>=2)ret=max(ret,25);
}
if(num[1]&&num[2]&&num[3]&&num[4]&&num[5])ret=max(ret,40);
if(num[2]&&num[3]&&num[4]&&num[5]&&num[6])ret=max(ret,40);
if(num[1]&&num[2]&&num[3]&&num[4])ret=max(ret,30);
if(num[2]&&num[3]&&num[4]&&num[5])ret=max(ret,30);
if(num[3]&&num[4]&&num[5]&&num[6])ret=max(ret,30);
return ret;
}
int dfs(int pos,vector<int> cur,int cnt){
if(cnt==0)return score(cur);
int ret=0;
for(int i=0;i<(1<<5);i++){
vector<int> b=cur;
int p=pos;
for(int j=0;j<5;j++){
if(i&(1<<j)){
b[j]=rolls[p++]-'0';
}
}
ret=max(ret,dfs(p,b,cnt-1));
}
return ret;
}
int bestScore(string rolls_) {
rolls=rolls_;
vector<int> cur(5,0);
FORE(i,0,5)cur[i]=rolls[i]-'0';
return dfs(5,cur,2);
}
};
class BestYahtzeeScore {
public:
int score(vector<int> cur){
int ret=0;
int num[7]={};
FORE(i,0,5)num[cur[i]]++;
FORE(i,1,7){
if(num[i]>=5)ret=max(ret,50);
if(num[i]>=4)ret=max(ret,cur[0]+cur[1]+cur[2]+cur[3]+cur[4]);
if(num[i]>=3)FORE(j,1,7)if(i!=j&&num[j]>=2)ret=max(ret,25);
}
if(num[1]&&num[2]&&num[3]&&num[4]&&num[5])ret=max(ret,40);
if(num[2]&&num[3]&&num[4]&&num[5]&&num[6])ret=max(ret,40);
if(num[1]&&num[2]&&num[3]&&num[4])ret=max(ret,30);
if(num[2]&&num[3]&&num[4]&&num[5])ret=max(ret,30);
if(num[3]&&num[4]&&num[5]&&num[6])ret=max(ret,30);
return ret;
}
int dfs(int pos,vector<int> cur,int cnt){
if(cnt==0)return score(cur);
int ret=0;
for(int i=0;i<(1<<5);i++){
vector<int> b=cur;
int p=pos;
for(int j=0;j<5;j++){
if(i&(1<<j)){
b[j]=rolls[p++]-'0';
}
}
ret=max(ret,dfs(p,b,cnt-1));
}
return ret;
}
int bestScore(string rolls_) {
rolls=rolls_;
vector<int> cur(5,0);
FORE(i,0,5)cur[i]=rolls[i]-'0';
return dfs(5,cur,2);
}
};