C++完全背包的提高板优化

Question

C++完全背包的提高板优化

这是本人的70分code，不知道有没有dalao优化一下呗

#include<bits/stdc++.h>
using namespace std;
struct TsYaya {int w,v;} a[2100];
int f[2100][2100];
int main()
{
    freopen("pack.in","r",stdin);
    freopen("pack.out","w",stdout);
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].v);

    for (int i=1;i<=n;i++)
     for (int j=1;j<=t;j++)
     {
        f[i][j]=f[i-1][j];
        if (j>=a[i].w) f[i][j]=max(f[i][j],f[i][j-a[i].w]+a[i].v);
     }
    printf("%d\n",f[n][t]);

    char ch;
    for (int i=1;i<=m;i++)
    {
        cin>>ch;
        int x,y;

        if (ch=='b')
        {
            scanf("%d",&x);
            if (x>0)
            {
                for (int i=1;i<=n;i++)
                 for (int j=t;j<=t+x;j++)
                  {
                     f[i][j]=f[i-1][j];
                     if (j>=a[i].w) f[i][j]=max(f[i][j],f[i][j-a[i].w]+a[i].v);
                 }
            }
            t+=x;
            printf("%d\n",f[n][t]);
        }

        if (ch=='a')
        {
            n++;
            scanf("%d%d",&a[n].w,&a[n].v);
            for (int j=1;j<=t;j++)
            {
                f[n][j]=f[n-1][j];
                if (j>=a[n].w) f[n][j]=max(f[n][j],f[n][j-a[n].w]+a[n].v);
            }
            printf("%d\n",f[n][t]);
        }

        if (ch=='c')
        {
            scanf("%d",&x);
            a[x].v=a[n].v;
            a[x].w=a[n].w;
            n--;
            for (int i=x;i<=n;i++)
             for (int j=1;j<=t;j++)
            {
                f[i][j]=f[i-1][j];
                if (j>=a[i].w) f[i][j]=max(f[i][j],f[i][j-a[i].w]+a[i].v);
            }
            printf("%d\n",f[n][t]);
        }
    }

    return 0;
}

据出题者说，要用到两个背包，但是本人听挂了，kk

Answer 1

https://blog.csdn.net/qq_41785863/article/details/83098960