Posted on 2008-08-17 10:09
oyjpart 阅读(2725)
评论(1) 编辑 收藏 引用 所属分类:
ACM/ICPC或其他比赛
PKU2690 Yahtzee
用搜索做，超时，郁闷。
正解：动态规划。
DP状态：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;
}
}
}