【昆明之前每天补一道区域赛银/铜牌题】2021上海 I-Steadily Growing Steam（01背包变形）
题意：给出n个物品的体积和价值，可以选择最多k个的物品体积翻倍，问能否分出俩个子集，使这俩个子集的体积和相同且价值和最大
考虑从01背包入手，01背包的状态转移方程f[i][j]表示前i个物品放入容量为j的背包里的最大价值，那么f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]
考虑此题怎么从01背包转换过来，先不考虑子集这个概念，只考虑翻倍，那么我们可以多开一维，f[i][j][k]表示前i个物品，翻了j个，放入容量为k的背包里的最大价值，那么f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k-w[i]],f[i-1][j-1][k-2*w[i]]
再考虑分割体积和相同这个概念，我们可以把一个物品的体积看成有正负，正的代表放入集合S，负的代表放入集合T，为了方便划分(负数下标不好处理)，我们就把边界成13*100=1300,那么最终答案就是max(f[n][0~t][1300]),转移方程就稍微变化了一点，因为有正有负，所以转移方程为
f[i][j][k]=max(f[i][j][k],f[i-1][j][k],f[i-1][j-1][k-w[i]]+v[i],f[i-1][j-1][k-2w[i]]+v[i],f[i-1][j-1][k+w[i]]+v[i],f[i-1][j-1][k+2w[i]]+v[i])
可以类似01背包一样开滚动数组优化掉一维，但是这题似乎不用？因为范围很小，直接暴力跑就行了。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+5;
const int M=1300;
const ll mod=1e9+7;
inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; }
inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
int w[105],v[105];
int f[105][105][2601];
signed main()
{
int n=read(),t=read();
memset(f,-INF,sizeof f);
f[0][0][M]=0;
rep(i,1,n)
v[i]=read(),w[i]=read();
//dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k],dp[i-1][j-1][k-w[i]]+v[i],dp[i-1][j-1][k-2*w[i]]+v[i],dp[i-1][j-1][k+w[i]]+v[i],dp[i-1][j-1][k+2*w[i]]+v[i])
rep(i,1,n)
rep(j,0,t)
rep(k,0,2ll*M)
{
f[i][j][k]=f[i-1][j][k];
if(k>=w[i]) f[i][j][k]=max(f[i][j][k],f[i-1][j][k-w[i]]+v[i]);
if(k>=2*w[i]&&j) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-2ll*w[i]]+v[i]);
if(k+w[i]<=M) f[i][j][k]=max(f[i][j][k],f[i-1][j][k+w[i]]+v[i]);
if(k+2*w[i]<=2*M&&j) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k+2ll*w[i]]+v[i]);
}
ll ans=-INF;
rep(i,0,t)
ans=max(ans,f[n][i][M]);
printf("%lld\n",ans);
}
