Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1448 Accepted Submission(s): 501
思路:可能存在左端点相同的多个区间,那么此时我们肯定选右端点最大的那个区间。现在将区间按左端点排序,d[i][j]表示在1~i坐标轴范围内选择j个区间的最大区间并。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<sstream> #include<cmath> #include<stack> #include<cstdlib> #include <vector> #include <set> #include<queue> #include<map> using namespace std; #define ll long long #define llu unsigned long long #define INF 0x3f3f3f3f #define PI acos(-1.0) const int maxn = 2e3+5; const ll mod = 1e9+7; const double eps = 1e-8; int n,m,k; int dp[maxn][maxn]; struct node { int l,r; }s[maxn]; bool cmp(node x,node y) { return x.l < y.l; } int main() { int t; scanf("%d",&t); int ca = 1; while(t--) { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d%d",&s[i].l,&s[i].r); memset(dp,0,sizeof dp); sort(s+1,s+m+1,cmp); int num = 0; int pos = 1; for(int len = 0;len < n;len++) { for(pos;pos<=m;) { if(s[pos].l == len+1) { num = max(num, s[pos].r - s[pos].l + 1); pos++; } else break; } for(int j=0;j<=k;j++) { dp[len+1][j] = max(dp[len+1][j],dp[len][j]); dp[len+num][j+1] = max(dp[len][j]+num,dp[len+num][j+1]); } if(num) num--; } printf("Case #%d: %d\n",ca++,dp[n][k]); } }
Alice’s Stamps HDU - 6249 (区间DP)
原文:https://www.cnblogs.com/smallhester/p/10397289.html