题目描述
给定n张牌，每张牌有ti与一个vi。你至多可选m张牌，将其ti翻倍。在翻倍结束后，从n张牌中找出若干数量的牌，将其分为两组，两组的ti之和相等。求出此时的最大的vi之和。
题解：引用lwz_159的博客
AC代码：
#include<bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=1e6+5;
const ll INF=1e18+5;
const ll mod=998244353;
long long Power(long long base, long long power) {
long long result = 1;
while (power > 0) {
if (power & 1) {
result = result * base % mod;
}
power >>= 1;
base = (base * base) % mod;
}
return result;
}
ll dp[2][105][5205];
ll v[105],w[205];
int main(){
int n,k;
sc(n);sc(k);
for(int i=1;i<=n;i++){
sl(v[i]);sl(w[i]);
}
for(int j=0;j<=k;j++)
for(int u=0;u<=5200;u++){
dp[0][j][u]=-1ll*INF;
if(u==2600) dp[0][j][u]=0;
}
for(int i=1;i<=n;i++){
ll t;t=w[i];
int x=i%2;
for(int j=0;j<=k;j++){
for(int u=0;u<=5200;u++){
dp[x][j][u]=dp[x^1][j][u];
if(u-t>=0) dp[x][j][u]=max(dp[x][j][u],dp[x^1][j][u-t]+v[i]);
if(u+t<=5200) dp[x][j][u]=max(dp[x][j][u],dp[x^1][j][u+t]+v[i]);
if(j){
if(u-2*t>=0) dp[x][j][u]=max(dp[x][j][u],dp[x^1][j][u-2*t]+v[i]);
if(u+2*t<=5200) dp[x][j][u]=max(dp[x][j][u],dp[x^1][j][u+2*t]+v[i]);
}
}
}
}
printf("%lld\n",dp[n%2][k][2600]);
}
/*
4 1
10 1
-5 3
5 1
6 1
*/
