题解 | #Steadily Growing Steam#

这题和失衡天平 (nowcoder.com)这道题很像，都是天平两端需要放东西，那么就把必然需要去维护一个天平两端重量差。但是这道题还有一个技能的使用，使用技能可以将点数加倍。所以这个技能的使用也得需要维护。那么就是维护一个技能的使用次数。

//将手上的牌分成两部分，如果两部分点数相同那么就得到这两部分的牌。
在开始之前还可以全选一些牌将其点数增加二倍。最后要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)

//将手上的牌分成两部分，如果两部分点数相同那么就得到这两部分的牌。
//在开始之前还可以全选一些牌将其点数增加二倍。最后要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;
}