Codeforces 1176F Destroy it!
题目链接
https://codeforces.com/contest/1176/problem/F
题目大意
有一个 $n$ 回合的游戏，每回合给你 $k$ 个花费和价值分别为 $c_i$ 和 $d_i$ 的卡牌。每回合可以以任意顺序使用总花费不超过 $3$ 的卡牌，每使用十张卡片，这第十张卡片的价值会翻倍。问最大的总价值是多少。
题目分析
对于所有的回合，定义 $f[i][j]$ 为进行到 $i$ 回合，使用了 $j$ 张卡的最大价值。那么需要考虑每一回合内的情况。对于每一回合，定义 $g[i][j][k][0/1]$ 为使用了前 $i$ 个卡牌，使用了 $j$ 张卡牌，共花费了 $k$，且有没有翻倍的卡的最大取值。显然这就是一个的背包问题，直接搞就可以。之后在考虑使用 $0$ 到 $3$ 张卡牌的情况对 $f$ 进行转移，注意一定要新加入的卡牌数和原来的卡牌数加起来超过 $10$ 的时候需要使用 $g[i][j][k][1]$ ，而其余情况需要使用 $g[i][j][k][0]$。最后取最大值即可。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 2e5 + 5;
long long inf = 0x3f3f3f3f3f3f3f3f;
int n, m, t;
long long f[maxn][15];
long long g[maxn][5][5][2];
int read(){
int x;
scanf("%d", &x);
return x;
}
int main(){
int i, j, k, l, r;
long long x, y;
n = read();
for(i=0;i<=n;i++){
for(j=0;j<=10;j++){
f[i][j] = -inf;
}
}
f[0][0] = 0;
for(i=1;i<=n;i++){
m = read();
for(l=0;l<=3;l++){
for(r=0;r<=3;r++){
g[0][l][r][0] = g[0][l][r][1] = -inf;
}
}
g[0][0][0][0] = 0;
for(j=1;j<=m;j++){
x = read();
y = read();
for(l=0;l<=3;l++){
for(r=0;r<=3;r++){
g[j][l][r][0] = g[j - 1][l][r][0];
g[j][l][r][1] = g[j - 1][l][r][1];
}
}
for(l=0;l<=2;l++){
for(r=0;r<=3-x;r++){
g[j][l + 1][r + x][0] = max(g[j][l + 1][r + x][0], g[j - 1][l][r][0] + y);
g[j][l + 1][r + x][1] = max(g[j][l + 1][r + x][1], max(g[j - 1][l][r][0] + 2 * y, g[j - 1][l][r][1] + y));
}
}
}
for(j=0;j<10;j++){
for(k=0;k<=3;k++){
long long maxa = -inf;
long long maxb = -inf;
for(l=0;l<=3;l++){
maxa = max(maxa, g[m][k][l][0]);
maxb = max(maxb, g[m][k][l][1]);
}
if(j + k >= 10){
f[i][(j + k) % 10] = max(f[i][(j + k) % 10], f[i - 1][j] + maxb);
}else{
f[i][j + k] = max(f[i][j + k], f[i - 1][j] + maxa);
}
}
}
}
long long ans = -inf;
for(i=0;i<10;i++){
ans = max(ans, f[n][i]);
}
printf("%lld\n", ans);
return 0;
}