Posted on 2008-08-17 10:09
oyjpart 閱讀(2743)
評論(1) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
PKU2690 Yahtzee
用搜索做，超時，郁悶。
正解：動態(tài)規(guī)劃。
DP狀態(tài)：dp[mask][i], mask代表用了多少種方案了，i代表前6種方案的得分。
因為前6種方式得分和超過63有加分，因此這一維是必須的。
DP向后推比較好寫。
核心代碼：
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
pre[0][0][0] = -1;
for(j = 0; j < (1<<13); ++j) {
int round = ones(j);
for(k = 0; k < 126; ++k) if(dp[j][k] != -1) {
for(o = 1; o < 14; ++o) if(!(j&(1<<(o-1)))) {
int add = 0;
if(o <= 6) add = s[round][o];
if(dp[j|(1<<(o-1))][k+add] < dp[j][k] + s[round][o]) {
dp[j|(1<<(o-1))][k+add] = dp[j][k] + s[round][o];
pre[j|(1<<(o-1))][k+add][0] = o;
pre[j|(1<<(o-1))][k+add][1] = s[round][o];
}
}
}
}
int max = -1, maxa = -1, maxb = -1, maxk;
for(i = 0; i < (1<<13); ++i) {
for(k = 0; k < 126; ++k) {
int now = dp[i][k];
if(k >= 63) now += 35;
if(now > max) {
max = now;
maxa = i;
maxb = k;
if(k >= 63) maxk = 35;
else maxk = 0;
}
}
}