46届ICPC上海站Steadily Growing Steam（DP）

写在前面

这是去年ICPC上海站，我们队伍获得铜尾的比赛，曹佬手撕三维DP怒秀我和郎队，现在来看，好像也没有那么难嘿嘿，可能是自己刷了一些DP题。

题意

给你一个$n$个物品，每个物品有$v,t$两个属性，$v$是值，$t$是点数，现在你需要从里面取出若干份分成两堆（也就是说有的可以不选），求两堆的点数相等的时候的两堆的值的最大值。嘿嘿，没这么简单，还有一个条件，你最多有$k$次操作，可以使其中一个点数翻倍，也就是说，有可能让其翻倍之后正好两堆相同，这个时候更大，不然难以找到匹配的让其相等。

思路

其实就是背包问题吧，主要就是一个翻倍的操作，从数据范围来看，$n,k$并不大，最大才$100$，点数最多也才$13$，所以我们定义一个数组dp[i][j][k]表示前$i$个物品，已经翻倍了$j$次，两堆的“分数”达到的$k$的最大值

这里$t$最大13，$n$最大$100$，那么直接令$M=1300$，然后分成AB两堆可以理解为：如果放在A堆，那么就加，如果放在B堆，那么就减。比如一开始是$k=0$，来了一个$t=5$的，放在A堆，这个时候$k=5$，这个时候来了一个$t=3$，如果放在A堆，这个时候是加法，$k=8$，这个$8$理解为$3+5$；那么如果这个放在B堆呢？$k=5-3=2$，我们最后只需要统计$k=0$的时候，这个时候是AB两堆相等的时候。

因为有负数，所以我们需要扩大起始点，令此时的$M$为“0”，也就是本来的$(-M,M)$变为了$(0,2*M)$，很常见的技巧，然后就进行背包即可。

我们发现每次只与上一次有关联，所以我用的回滚数组，其实开三维也行，我当时是怕爆。

代码

int f[110][2630],g[110][2630];
inline void Case_Test()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>a[i]>>b[i];
    memset(f,233,sizeof(f));
    f[0][M]=0;
    for (int p=1;p<=n;p++)
    {
        memcpy(g,f,sizeof(f));
        for (int i=0;i<p&&i<=k;i++)
        {
            for (int j=0;j<2*M;j++)
            {
                if (b[p]<=j) g[i][j]=Max(g[i][j],f[i][j-b[p]]+a[p]);//不翻倍 +
                if (b[p]+j<=2*M) g[i][j]=Max(g[i][j],f[i][j+b[p]]+a[p]);//不翻倍 -
                if (b[p]*2<=j&&i>0) g[i][j]=Max(g[i][j],f[i-1][j-b[p]*2]+a[p]);//翻倍 +
                if (b[p]*2+j<=2*M&&i>0) g[i][j]=Max(g[i][j],f[i-1][j+b[p]*2]+a[p]);//翻倍 -
            }
        }
        memcpy(f,g,sizeof(g));
    }
    ans=-1e15;
    for (int i=0;i<=k;i++)
        ans=Max(ans,g[k][M]);//k可以不用完
    cout<<ans;
}