题解 | #Steadily Growing Steam#

没想到做了一道ICPC的原型题目 这道题居然有5种转移状态

//将手上的牌分成两部分，如果两部分点数相同那么就得到这两部分的牌。
//在开始之前还可以全选一些牌将其点数增加二倍。最后要value最大的方式。
//状态转移一共有五种情况：
//1、不选当前的卡片：dp[i][j][k] = dp[i-1][i][j];
//2、选当前的卡片但将其放到点数大的那一个里面(不使用技能)：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k+a[i].point]+a[i].v)
//4、选当前的卡片但将其放到点数小的那一个里面(不使用技能)：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][abs(k-a[i].point)]+a[i].v)
//3、选当前的卡片但将其放到点数大的那一个里面(使用技能)：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k+a[i].point]+a[i].v)
//5、选当前的卡片但将其放到点数小的那一个里面(使用技能)：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][abs(k-a[i].point)]+a[i].v)
#include <bits/stdc++.h>

using namespace std;
#define int long long
const int inf = 0x3f3f3f3f;
struct Node {
    int v, t;
} a[100+10];
//i代表某个卡片，j代表使用技能的次数，k表示两种中点数的差值。
int dp[100+10][100+10][1301];
int n, k;

signed main() {
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>a[i].v>>a[i].t;
    }
    memset(dp, -inf, sizeof(dp));
    dp[0][0][0] = 0;
    for (int i=1;i<=n;i++) 
        for (int j=0;j<=k;j++) 
            for (int k=0;k<=1301;k++) {
                dp[i][j][k] = dp[i-1][j][k];
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][abs(k+a[i].t)]+a[i].v);
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][abs(k-a[i].t)]+a[i].v);
                if (j!=0) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][abs(k+a[i].t*2)]+a[i].v);
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][abs(k-a[i].t*2)]+a[i].v);
                }
            }
    int ans = 0;
    for (int j=0;j<=k;j++) {
        ans = max(ans, dp[n][j][0]);
    }
    cout<<ans;
    return 0;
}
一个01背包问题的变形

状 态 表 示 ： f [ i ] [ j ] [ k ] 表 示 从 前 i 张 牌 中 ， 最 多 使 用 j 次 技 能 ， 两 组 牌 的 t [ i ] 和 之 差 为 k 时 的 s [ i ] 之 和 最 大 为 多 少 状态表示：f[i][j][k]表示从前i张牌中，最多使用j次技能，两组牌的t[i]和之差为k时的s[i]之和最大为多少状态表示：f[i][j][k]表示从前i张牌中，最多使用j次技能，两组牌的t[i]和之差为k时的s[i]之和最大为多少

因 为 k 表 示 的 差 ， 所 有 k 的 范 围 理 论 上 是 [ − 2600 , 2600 ] ， 但 是 数 组 下 标 又 不 能 有 负 数 ， 因 此 我 们 可 以 让 k = k + 2600 ， 因为k表示的差，所有k的范围理论上是[-2600,2600]，但是数组下标又不能有负数，因此我们可以让k=k+2600，因为k表示的差，所有k的范围理论上是[−2600,2600]，但是数组下标又不能有负数，因此我们可以让k=k+2600，这 样 k 的 范 围 就 变 为 了 [ 0 , 5200 ] 。 问 题 解 决 。 这样k的范围就变为了[0,5200]。问题解决。这样k的范围就变为了[0,5200]。问题解决。