Schrödinger’s Knapsack

总结

坑点：大水题，大水题，我是个大菜逼，TLE 了好几发，发现他这个条件给的用memset太不划算了，还不如for循环，就因为这个卡了好几发，真鸡儿悲伤

题意

背包问题的变形，虽然跟背包相去甚远，但还是一个dp问题，给定一个背包容量，有两大类物品，这两大类物品，每一种物品都有固定的价值，但是体积不相同，而且放入每一个物品的增加的价值等于价值*（加入本物品后剩余的容量）

算法分析

对与每一个大类按体积进行升序排序，因为肯定优先选择体积小的物品，排序后预处理，suma[i] 代表第一类到第i个物品的体积，sumb[i] 代表到第二类物品到第i个物品的体积，dp[i][j] 代表选择 第一类物品选择i个，第二个物品选择j个的最大价值
然后进行dp,

d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] + k 1 ∗ ( c − s u m a [ i ] − s u m b [ j ] ) , d p [ i ] [ j − 1 ] + k 2 ( c − s u m a [ i ] − s u m b [ j ] )

n*m的复杂度
参考代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2000+10;
int a[maxn];
int b[maxn];
long long  F[maxn][maxn];
int n,m;
long long suma[maxn],sumb[maxn];
int k1,k2,c;
int len1,len2;
void init(void)
{

    len1 = len2 = 0;
    scanf("%d %d %d",&k1,&k2,&c);
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
    }
    for(int j = 1; j <= m; ++j)
    {
        scanf("%d",&b[j]);
    }
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    len1 = n,len2 = m;
    for(int i = 1; i <= len1; ++i)
    {
        suma[i] = suma[i-1] + a[i];
        if(suma[i] >= c)
        {
            len1 = i;
            break;
        }
    }

    for(int i = 1; i <= len2; ++i)
    {
        sumb[i] = sumb[i-1] + b[i];
        if(sumb[i] >= c)
        {
            len2 = i;
            break;
        }
    }
}
long long process(void)
{
    long long ans = 0;
    for(int i = 0; i <= len1; ++i)
    {
        for(int j = 0; j <= len2; ++j)
        {
            F[i][j] = 0;
            long long tmp = c - suma[i] - sumb[j];
            if(tmp <= 0)
                continue;
            if(i > 0)
                F[i][j] = F[i-1][j]+k1*tmp;
            if(j > 0)
                F[i][j] = max(F[i][j],F[i][j-1]+k2*tmp);
            ans = max(ans,F[i][j]);
        }
    }
    return ans;
}
int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        // memset(F,0,sizeof(F));
        init();
        printf("%lld\n",process());
    }

    return 0;
}