采药

int n;
const int N=110;
int w[N],v[N];
int f[1010];
void solve()
{
    int m,n;
    cin>>m>>n;
    rep(i,1,n)cin>>v[i]>>w[i];
    rep(i,1,n)
    {
        dwn(j,m,v[i])
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
}

装箱问题

int n;
const int N=20010;
int f[N];
void solve()
{
    int m,n;
    cin>>m>>n;
    rep(i,1,n)
    {
        int v;
        cin>>v;
        dwn(j,m,v)
            f[j]=max(f[j],f[j-v]+v);
    }
    cout<<m-f[m]<<endl;
}

宠物小精灵之收复

int n,m,t;
const int N=1010;
int v1[N],v2[N];
int f[N][N];
void solve()
{
    cin>>m>>t>>n;
    rep(i,1,n)cin>>v1[i]>>v2[i];
    rep(i,1,n)
        dwn(j,m,v1[i])
            dwn(k,t,v2[i])
                f[j][k]=max(f[j][k],f[j-v1[i]][k-v2[i]]+1);
    cout<<f[m][t-1]<<' ';
    int res=INF;
    rep(i,0,t-1)
    {
        if(f[m][i]==f[m][t-1])
            res=min(res,i);
    }
    cout<<t-res<<endl;

}

数字组合

int n,m;
const int N=110,M=10010;
int f[M];
void solve()
{
    cin>>n>>m;
    f[0]=1;
    rep(i,1,n)
    {
        int v;
        cin>>v;
        dwn(j,m,v)
            f[j]+=f[j-v];
    }
    cout<<f[m]<<endl;
}

买书

int n,m;
int f[1010];
int v[5]={0,10,20,50,100};
void solve()
{
    n=4;
    cin>>m;
    f[0]=1;
    rep(i,1,n)
    {
        rep(j,v[i],m)
            f[j]+=f[j-v[i]];
    }
    cout<<f[m]<<endl;
}

货币系统

int n,m;
int f[3010];
int v[3010];
void solve()
{
    cin>>n>>m;
    rep(i,1,n)cin>>v[i];
    f[0]=1;
    rep(i,1,n)
    {
        rep(j,v[i],m)
            f[j]+=f[j-v[i]];
    }
    cout<<f[m]<<endl;
}

庆功会

int n,m;
const int N=510,M=6010;
int f[N][M];
int v[N],w[N],s[N];
void solve()
{
    cin>>n>>m;
    rep(i,1,n)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
        }
    }
    cout<<f[n][m]<<endl;
}

混合背包

{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int v,w,s;
        cin>>v>>w>>s;
        if(!s)//完全背包
        {
            for(int j=v;j<=m;j++)
                f[j]=max(f[j],f[j-v]+w);
        }
        else
        {
            if(s==-1)s=1;//01背包转多重背包
            for(int k=1;k<=s;k*=2)//多重背包二进制优化，优化选择次数
            {
                for(int j=m;j>=k*v;j--)
                    f[j]=max(f[j],f[j-k*v]+k*w);
                    s-=k;
            }
            if(s>0)
            {
                for(int j=m;j>=s*v;j--)
                {
                    f[j]=max(f[j],f[j-s*v]+s*w);
                }
            }
        }
    }
    cout<<f[m]<<endl;
}

二位费用背包问题

int f[1010][1010];
void solve()
{
    int N,V,M;
    cin>>N>>V>>M;
    rep(i,1,N)
    {
        int v,m,w;
        cin>>v>>m>>w;
        dwn(j,V,v)
        {
            dwn(k,M,m)
            {
                f[j][k]=max(f[j][k],f[j-v][k-m]+w);
            }
        }
    }
    cout<<f[V][M]<<endl;
}

潜水员

int f[1010][1010];
int m,n,k;
void solve()
{
    cin>>m>>n>>k;
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    rep(i,1,k)
    {
        int a,b,c;
        cin>>a>>b>>c;
        dwn(j,m,0)
        {
            dwn(h,n,0)
            {
                f[j][h]=min(f[j][h],f[max(0ll,j-a)][max(0ll,h-b)]+c);
            }
        }
    }
    cout<<f[m][n]<<endl;
}

机器分配

int f[30][30];
int m,n;
int w[30][30];
int maxv;
vector<int>res;
void dfs(int u,vector<int>&v,int sum,int cnt)
{
    if(u>n||cnt<0)
    {
        if(sum>maxv)
        {
            maxv=sum;
            res=v;
        }
        return;
    }
    for(int i=0;i<=min(cnt,m);i++)
    {
        sum+=w[u][i];
        v.pb(i);
        dfs(u+1,v,sum,cnt-i);
        v.pop_back();
        sum-=w[u][i];
    }
}
void solve()
{
    cin>>n>>m;
    rep(i,1,n)
        rep(j,1,m)
            cin>>w[i][j];
    vector<int>v;
    dfs(1,v,0,m);
    cout<<maxv<<endl;
    for(int i=1;i<=n;i++)
        cout<<i<<' '<<res[i-1]<<endl;
}

开心的金明

int n,m;
const int N=30010;
int f[N];
void solve()
{
    cin>>n>>m;
    rep(i,1,m)
    {
        int v,p;
        cin>>v>>p;
        dwn(j,n,v)
            f[j]=max(f[j],f[j-v]+v*p);
    }
    cout<<f[n]<<endl;
}