20 pts 暴力 (实际80)

include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int c[3][200];
int a[2000];
int b1,b2;
int d[3][200];
int u[3][200];
int ans=1e15;
int dis,wk;
int ned1,ned2;
void dfs(int now)
{
    if (dis+wk>ans) return;
    if (ned1>b1 || ned2>b2) return;
    if (now==n && ned1<=b1 && ned2<=b2)
    {
//        printf("%lld %lld\n",dis,wk);
        ans=min(ans,dis+wk);
        return;
    }
    int res1=dis,res2=wk;
    int res3=ned1,res4=ned2;
    for (int i=0;i<=a[now+1];i++)
    {
        int res=a[now+1]-i;
        if (i!=0) ned1+=c[1][now+1];
        if (res!=0) ned2+=c[2][now+1];
        dis=max(dis,max(d[1][now+1]*i,d[2][now+1]*res));
        wk=max(wk,max(u[1][now+1]*i,u[2][now+1]*res));
        dfs(now+1);
        dis=res1; wk=res2;
        ned1=res3,ned2=res4;
    }
}

20pts 背包

int f[59][59][59];
if (ok==0)
    {
        memset(f,0x3f,sizeof(f));
        for (int i=0;i<=b1;i++)
            for (int j=0;j<=b2;j++) f[0][i][j]=0;
        for (int i=1;i<=n;i++) 
        {
            for (int j=0;j<=b1;j++)
            {
                for (int k=0;k<=b2;k++)
                {
//                    f[i][j][k]=f[i-1][j][k];
                    for (int l=0;l<=a[i];l++)
                    {
//                        if (l>j || a[i]-l>k) continue;
                        int w=j,v=k;
                        if (l!=0) w=j-c[1][i];
                        if (a[i]-l!=0) v=k-c[2][i];
                        if (w<0 || v<0) continue;
                        int a1=l,a2=a[i]-l;
                        f[i][j][k]=min(f[i][j][k],max(f[i-1][w][v],max(a1*u[1][i],(a2)*u[2][i])));
                    }
                }
            }
        }
        printf("%lld\n",f[n][b1][b2]);
        return 0;
    }

20 pts(挂了一个点，不知道为啥) 背包

int f[59][59][59];
int g[59][59][59];
int h[59][59][59];
if (ok2==0)
    {
        memset(f,0x3f,sizeof(f));
        for (int i=0;i<=b1;i++)
            for (int j=0;j<=b2;j++) f[0][i][j]=0;
        for (int i=1;i<=n;i++) 
        {
            for (int j=0;j<=b1;j++)
            {
                for (int k=0;k<=b2;k++)
                {
//                    f[i][j][k]=f[i-1][j][k];
                    for (int l=0;l<=a[i];l++)
                    {
//                        if (l>j || a[i]-l>k) continue;
                        int w=j,v=k;
                        if (l!=0) w=j-c[1][i];
                        if (a[i]-l!=0) v=k-c[2][i];
                        if (w<0 || v<0) continue;
                        int a1=l,a2=a[i]-l;
                        if (v!=k)
                        {
                            if (f[i][j][k]>max(d[2][i],g[i-1][w][v])+max(h[i-1][w][v],u[2][i]))
                            {
                                f[i][j][k]=max(d[2][i],g[i-1][w][v])+max(h[i-1][w][v],u[2][i]);
                                g[i][j][k]=max(d[2][i],g[i-1][w][v]);
                                h[i][j][k]=max(h[i-1][w][v],u[2][i]);
                            }
                        }
                        else if (w!=j)
                        {
                            if (f[i][j][k]>max(d[1][i],g[i-1][w][v])+max(h[i-1][w][v],u[1][i]))
                            {
                                f[i][j][k]=max(d[1][i],g[i-1][w][v])+max(h[i-1][w][v],u[1][i]);
                                g[i][j][k]=max(d[1][i],g[i-1][w][v]);
                                h[i][j][k]=max(h[i-1][w][v],u[1][i]);
                            }
                        }
                    }
                }
            }
        }
        int ans=1e15;
//        for (int i=0;i<=b1;i++)
//            for (int j=0;j<=b2;j++) ans=min(f[n][i][j],ans); 
        printf("%lld\n",f[n][b1][b2]);
        return 0;    
    }