首页 > 代码库 > SPOJ RENT 01背包的活用+二分

SPOJ RENT 01背包的活用+二分

2024-07-14 12:45:10   225人阅读

这个题目给定N航班的发出时间和结束时间以及价值，要求不冲突时间的最大价值

第一时间想到经典的N方DP，即对航班按发出时间排一下序之后每个i对前面的都扫一遍

时间过不了N有10万，只能想优化了，一开始想了个用树状数组记录每次加入某个航班之后 后面的所有在结束时间后的区间全部可以加一个最大值，但是首先时间区间的量更大，而且树状数组不好这么操作

后来实在没见过这种DP，还是看的别人的算法，还是挺叼的，不过其实还是沿用的背包思想

对于每个航班区间，我只需要考虑取或者不取，这样的话，对航班按出发时间S排序，从后往前，对该航班结束时间T找到 i+1到n中满足出发时间Ti<=Sk(i<k<=n)的，由于找到的已经是最优值的，所以直接+现在的价值，当然，如果不取该区间的话 dp[i]=dp[i+1]即可.用了典型的01背包思想。因为查找可以用二分，所以把时间复杂度控制在NlogN，不会超时

当然，为什么要从后往前扫值得深思，首先这样扫过来肯定是对的，因为他的子结构只会在他后面（即满足结束时间《=发出时间的），而且他们已经是最优了。反过来如果从前面开始扫，那他们的子结构还是在后面，但后面的还没访问过，不是最优值，所以无法转移。因此这就是为什么转移是这样的

这个题目真的不错，DP模型很经典，但是状态转移很新颖

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;struct node{    int s,d,p;    bool operator < (const node& rhs) const{        return s<rhs.s;    }}rent[10010];const int N = 10010;int dp[N];int bs(int v,int L,int R){    int mid;    while (L<R){       mid=(L+R)>>1;       if (v<=rent[mid].s) R=mid;       else  L=mid+1;    }    return L;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        memset(dp,0,sizeof dp);        int n;        scanf("%d",&n);        for (int i=0;i<n;i++){            scanf("%d%d%d",&rent[i].s,&rent[i].d,&rent[i].p);            rent[i].d=rent[i].s+rent[i].d;        }        sort(rent,rent+n);        memset(dp,0,sizeof dp);        for (int i=n-1;i>=0;i--){            dp[i]=dp[i+1];            int loc=bs(rent[i].d,i+1,n);            dp[i]=max(dp[i],dp[loc]+rent[i].p);        }        printf("%d\n",dp[0]);    }    return 0;}

　　


联系
我们