背包总结

P3859

TJOI的水题（黄题难度的紫题）

定义f[j]表示用了j时间时获得宝石的最大价值。~~是的只用一维滚动就行~~

因此转移方程：

    f[j]=max(max(f[j],f[j-1]),f[j-t]+v);

可以提前把宝石按限制时间排个序，也可以不排

P1049

背包的简单变形。

设f[i] (bool类型)为能否将i的空间装满。则转移方程:

    f[0]=1;
    for(int i=1;i<=n;++i){
        for(int j=v;j>=a[i];--j){
            if(f[j-a[i]])f[j]=1;    
        }
    }

P1064

一道好题

因为每个物品的状态总共就3种，即自己，左儿子和右儿子，所以就设所有物品都有儿子。

设f[i]表示价格为i时价格与权重的乘积最大值。则转移方程：

f[0]=0;
    ans=0;
    for(int i=1;i<=m;++i){
        if(!v[i][0])continue;
        for(int j=n;j>=v[i][0];--j){
            if(v[i][1] && v[i][2] && j>=v[i][0]+v[i][1]+v[i][2])f[j]=max(f[j],f[j-v[i][0]-v[i][1]-v[i][2]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]+v[i][2]*w[i][2]);
            if(v[i][1] && j>=v[i][0]+v[i][1])f[j]=max(f[j],f[j-v[i][0]-v[i][1]]+v[i][0]*w[i][0]+v[i][1]*w[i][1]);
            if(v[i][2] && j>=v[i][0]+v[i][2])f[j]=max(f[j],f[j-v[i][0]-v[i][2]]+v[i][0]*w[i][0]+v[i][2]*w[i][2]);
            if(j>=v[i][0])f[j]=max(f[j],f[j-v[i][0]]+v[i][0]*w[i][0]);
            ans=max(f[j],ans);
        }
    }

注意附件不能将他的主件栏填进去(v[i][0],w[i][0])。

//读入
for(int i=1;i<=m;++i){
        scanf("%d%d%d",&v1,&w1,&p1);
        if(p1==0)v[i][0]=v1,w[i][0]=w1;
        else{
            if(v[p1][1])v[p1][2]=v1,w[p1][2]=w1;
            else v[p1][1]=v1,w[p1][1]=w1;
        }
    }

P1651

设f[i][j]表示前i个物品搭出的高度相差j的两个塔中最高的塔的高度。

这样既能将状态表示全，又能避免用两维的高度导致MLE。事实上i那一维可以滚存优化掉。

注意因为转移中会出现负数，所以要将第二维开两倍，将中间点500000设为零点。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10,M=53,P=1e6;
int f[2][N];
int n;
int a[M];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    int ans=-0x7fffffff;
    memset(f,-0x3f,sizeof f);
    f[0][500000]=0;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=P;++j){
            f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j]);
            if(j-a[i]>=0)f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j-a[i]]+a[i]);
            if(j+a[i]<=P)f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j+a[i]]);
            if(j==500000)ans=max(ans,f[i%2][j]);
        }
    }
    if(ans>0)printf("%d",ans);
    else printf("-1");
    return 0;
}
/*
20
188242 313 1991 4207 2483 1763 224 16 582 22943 111653 23787 16820 12415 1270 3032 2293 5221 396 42
*/

P4823

首先有个贪心的性质：

对于每个小矮人，一定是逃生能力弱，即\(a+b\)较小的人先逃比能力强的人先逃的不会更差。

因为能力弱的人如果不先逃，以后就可能逃不出去了。

不会出现能力强的先逃后弱的能逃，而弱的先逃强的就逃不了的情况。

只要弱的逃了强的逃不了，那强的逃了弱的也跑不了。因为后一个逃的脚底下高度是一定的。

有了这个性质后就可以用背包解决每个矮人是否要逃出去。因为可能它\(a\)特别大，不逃对人梯的贡献更大。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2200;
struct node{
    int a,b;
}q[N];
bool cmp(node a,node b){
    return a.a+a.b<b.a+b.b;
}
int n,h;
int dp[N];
int main(){
    memset(dp,-0x3f,sizeof dp);
    dp[0]=0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d%d",&q[i].a,&q[i].b),dp[0]+=q[i].a;
    scanf("%d",&h);
    sort(q+1,q+n+1,cmp);
    for(int i=1;i<=n;++i){
        for(int j=i;j>=1;--j){
            if(dp[j-1]+q[i].b>=h)dp[j]=max(dp[j],dp[j-1]-q[i].a);
        }
    }
    for(int i=n;i>=0;--i){
        if(dp[i]>=0){
            printf("%d",i);
            return 0;   
        }
    }

    return 0;
}

* 结论：当背包的转移收到顺序影响，又不能确定物品拿取的具体顺序，可以寻找贪心的性质,排序后做背包。

P3961

可以用斜率存储所有点的信息，注意处理\(x=0\)即斜率不存在的情况。

之后，对于每一组金子，可以将第\(i\)个的时间价值和前\(i-1\)个并再一起，表示连续取\(i\)个金子。

在做背包时，同一组只能选一个，所以注意顺序。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=320,M=5e4+10,K=200;
int f[M],top[N+N][N],nxt[N],head[N+N][N],l[N],r[N];
int n,T,cnt,tot;
struct query{
    int x,y,t,v;
    double k;
}q[N];
struct item{
    int t,v;
}c[N]; 
bool cmp(query a,query b){
    if(a.k==b.k)return a.y<b.y;
    else return a.k<b.k;
} 
void print1(){
    for(int i=1;i<=tot;++i){
        for(int k=l[i];k<=r[i];++k){
            cout<<c[k].t<<" "<<c[k].v<<endl;        
        }
    }
}

signed main(){
    scanf("%lld%lld",&n,&T);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld%lld",&q[i].x,&q[i].y,&q[i].t,&q[i].v);
        if(q[i].x!=0)q[i].k=q[i].y*1.0/(q[i].x*1.0);
        else q[i].k=N;
    }
    sort(q+1,q+n+1,cmp);
    tot=0;
    for(int i=1;i<=n;++i){
        int x=q[i].x,y=q[i].y;
        if(q[i].k!=q[i-1].k || i==1){
            r[tot]=i-1;
            ++tot;
            l[tot]=i;
        }
        c[i].t+=q[i].t;
        c[i].v+=q[i].v;
        if(q[i].k==q[i-1].k && i!=1){
            c[i].t+=c[i-1].t;
            c[i].v+=c[i-1].v;
        }
    }
    r[tot]=n;
    //print1();
    //memset(f,-0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=tot;++i){
        for(int j=T;j>=c[l[i]].t;--j){
            for(int k=l[i];k<=r[i];++k){
                if(j>=c[k].t)f[j]=max(f[j],f[j-c[k].t]+c[k].v);
            }
        }
    }
    int maxn=0;
    for(int i=0;i<=T;++i){
        maxn=max(maxn,f[i]);
    }
    printf("%lld",maxn);
    return 0;
}
/*
4 17
0 10 2 3
-2 3 1 1
-4 6 2 2
-6 8 15 9

3 10
1 1 13 1
2 2 2 2
1 3 4 7
*/

P1156

这题唯一的坑点就是同一时间会放多个垃圾。

这时要用链表/vector存储一下，并且同一时刻的垃圾是有先后顺序的，即高度可以累加。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=4400,T=1000,K=220;
int f[N][K];
int D,G,tot;
int cnt[N],tim[N];
struct node {
    int h,f;
} c[N][K];
int main() {
    //freopen("P1156_2.in","r",stdin);
    scanf("%d%d",&D,&G);
    int sum=10;
    for(int i=1,tmp; i<=G; ++i) {
        scanf("%d",&tmp);
        ++cnt[tmp];
        scanf("%d%d",&c[tmp][cnt[tmp]].f,&c[tmp][cnt[tmp]].h);
        sum+=c[tmp][cnt[tmp]].f;
    }
    memset(f,-1,sizeof f);
    f[0][0]=10;
    for(int i=1; i<=sum; ++i) {
        for(int j=0; j<=cnt[i]; ++j) {
            tim[++tot]=i;
            for(int h=D; h>=0; --h) {
                int t1=tim[tot]-tim[tot-1];
                if(c[i][j].h) {
                    if(h>=c[i][j].h && f[tot-1][h-c[i][j].h]-t1>=0)f[tot][h]=max(f[tot][h],f[tot-1][h-c[i][j].h]-t1);
                    if(f[tot-1][h]-t1>=0)f[tot][h]=max(f[tot][h],f[tot-1][h]-t1+c[i][j].f);
                }
                if(f[tot-1][h]-t1>=0)f[tot][h]=max(f[tot][h],f[tot-1][h]-t1);
            }
        }

    }
    int maxn=-1;
    for(int i=0; i<=tot; ++i) {
        for(int h=0; h<=D; ++h) {
            //cout<<f[i][h]<<" ";
            if(f[i][h]>=0)maxn=max(maxn,tim[i]);
        }
        //cout<<endl;
        if(f[i][D]>=0) {
            printf("%d\n",tim[i]);
            return 0;
        }
    }
    printf("%d\n",maxn);
    /*for(int i=0;i<=tot;++i){
        cout<<tim[i]<<" ";
    }*/
    return 0;
}
/*
100 4
5 4 9
9 3 2
12 6 10
13 1 1
*/

P5662

一个很重要的想法：每天卖的东西当天还能买回来。这让我们能够简化状态。

此时如果我们向持有某物品\(n\)天，我们就第\(1\)天买，第\(2\)天卖，再第\(2\)天买，第\(3\)天卖，以此类推。

这样我们就不需要记录每天物品的个数，只需要记录转天的钱数即可。

设\(f[k]\)表示第\(i\)天，第\(j\)个物品时还剩\(k\)元，明天能获得的最大的钱数。

那么有:

\[ f[k-c[i][j]]=max(f[k-c[i][j]],f[k]+c[i+1][j]-c[i][j]) \]

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long 
using namespace std;
const int N=110,M=10010,T=110;
int n,m,t,ans;
int c[T][N];
int f[M];
signed main(){
    scanf("%lld%lld%lld",&t,&n,&m);
    for(int i=1;i<=t;++i){
        for(int j=1;j<=n;++j){
            scanf("%lld",&c[i][j]);
        }
    } 
    f[m]=0;
    ans=m;
    for(int i=1;i<=t;++i){
        memset(f,-1,sizeof f);
        f[ans]=ans;
        for(int j=1;j<=n;++j){
            for(int k=ans;k>=c[i][j];--k){
                if(f[k]==-1)continue;
                f[k-c[i][j]]=max(f[k-c[i][j]],f[k]+c[i+1][j]-c[i][j]);
            }
        }
        for(int i=0;i<=ans;++i)ans=max(ans,f[i]);
    }
    printf("%lld",ans);
    return 0;
}