這是一道很好的訓練dp的題，并且有很多細節需要注意
原題如下：
饑餓的奶牛
描述
牛在飼料槽前排好了隊。飼料槽依次用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的理解更深刻。所以，快去做一做吧！
浙公網安備 33010602011771號