描述
牛在饲料槽前排好了队。饲料槽依次用1到N(1≤N≤2000) 编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。
约翰提供 N个区间的清单。一个区间是一对整数 l,r(1≤l≤r≤N)，表示一些连续的饲料槽，比如 1-3,7-8,3−4 等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。
当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。
在上面的例子中，1-3 和 3−4 是重叠的；聪明的牛选择1−3，7−8 ，这样可以吃到 5个槽里的东西。
输入
第一行，整数 N(1≤N≤2000)。
第 2 到 N+1 行，每行两个整数，表示一个区间，较小的端点在前面。
输出
仅一个整数，表示最多能吃到多少个槽里的食物。
输入样例 1
3 1 3 7 8 3 4
输出样例 1
5
看完题目，我们会感觉很简单，但又无从下手。因为这里包含了左边界和右边界，所以我们先定义一个结构体。
struct node
{
long long b,c;
}a[100010];
然后对它进行排序，或许会有点思路
sort(a+1,a+1+n);//排序，为之后dp做准备
因为这是结构体的排序，所以我们需要自定义一个排序函数
bool cmp( node x, node y)//自定义排序方法 { if(x.c!=y.c) return x.c<y.c; return x.b<y.b; }
sort(a+1,a+1+n,cmp);//排序，为之后dp做准备
然后便开始dp
ans=dp[1]=a[1].c-a[1].b+1;//这有个小细节，就是需+1后结果才正确 for(long long i=2;i<=n;i++) { dp[i]=a[i].c-a[i].b+1;//需+1 for(long long j=1;j<=i-1;j++) { if(a[j].c<a[i].b)//如果后一个的左边界比前一个的右边界大 { dp[i]=max(dp[i],dp[j]+(a[i].c-a[i].b+1));//dp求最大值 ，同样需+1 } } ans=max(ans,dp[i]);//取最大值 }
于是，代码便出来了
#include<bits/stdc++.h> using namespace std; long long n,ans; struct node { long long b,c; }a[100010]; bool cmp( node x, node y)//自定义排序方法 { if(x.c!=y.c) return x.c<y.c; return x.b<y.b; } long long dp[100010]; int main() { cin>>n; for(long long i=1;i<=n;i++) { cin>>a[i].b>>a[i].c; } sort(a+1,a+1+n,cmp);//排序，为之后dp做准备 for(long long i=1;i<=n;i++) { cout<<a[i].b<<‘ ‘<<a[i].c<<endl; } ans=dp[1]=a[1].c-a[1].b+1;//这有个小细节，就是需+1后结果才正确 for(long long i=2;i<=n;i++) { dp[i]=a[i].c-a[i].b+1; for(long long j=1;j<=i-1;j++) { if(a[j].c<a[i].b)//如果后一个的左边界比前一个的右边界大 { dp[i]=max(dp[i],dp[j]+(a[i].c-a[i].b+1));//dp求最大值 } } ans=max(ans,dp[i]);//取最大值 } cout<<ans; return 0; }
这是一道很好的dp题，可以使我们对dp的理解更深刻。所以，快去做一做吧！
原文：https://www.cnblogs.com/cymcym/p/13519984.html