poj3616（LIS简单变式）

 题目链接：http://poj.org/problem?id=3616

思路：

我的第一反应是背包，因为每个interval要么选择要么不选，后来发现状态方程很难写出来。后来想一想发现就是LIS的简单变式。先按照starting hours给数据排序，那么选择的顺序也就是排序后的顺序，用dp[i]表示以第i个interval结尾能获得最多的milk，状态转移方程就是dp[i]=max(dp[i],dp[j]+a[i].c)（a[j].e+r<=a[i].s,j<i）。由于上升子序列的长度最长的不一定是milk最多的，所以需要使用LIS的O(n^2)算法。另外记住需要初始化dp，即dp[i]=a[i].c。最后选择最大的dp[i]，就是所求答案。

详见代码：

#include<cstdio>
#include<algorithm>
using namespace std;

struct node{
    int s,e,c;
}a[1005];

bool cmp(node x,node y){
    return x.s<y.s;
}
int n,m,r,res,dp[1005];

int main(){
    scanf("%d%d%d",&n,&m,&r);
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].c);
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;++i) dp[i]=a[i].c;
    for(int i=2;i<=m;++i){
        for(int j=i-1;j>=1;--j)
            if(a[j].e+r<=a[i].s)
                dp[i]=max(dp[i],dp[j]+a[i].c);
        if(dp[i]>res) res=dp[i];
    }
    printf("%d
",res);
    return 0;
}