首页 > 其他 > 详细

Alice’s Stamps HDU - 6249 (区间DP)

时间:2019-02-18 20:14:30      阅读:219      评论:0      收藏:0      [点我收藏+]

点击传送

 

Alice’s Stamps

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1448    Accepted Submission(s): 501


Problem Description
Alice likes to collect stamps. She is now at the post office buying some new stamps.
There are N different kinds of stamps that exist in the world; they are numbered 1 through N. However, stamps are not sold individually; they must be purchased in sets. There are M different stamp sets available; the ith set contains the stamps numbered Li through Ri. The same stamp might appear in more than one set, and it is possible that one or more stamps are not available in any of the sets.
All of the sets cost the same amount; because Alice has a limited budget, she can buy at most K different sets. What is the maximum number of different kinds of stamps that Alice can get?
 

 

Input
The input starts with one line containing one integer T, the number of test cases.T test cases follow.
Each test case begins with a line containing three integers: NM, and K: the number of different kinds of stamps available, the number of stamp sets available, and the maximum number of stamp sets that Alice can buy.
M lines follow; the ithoftheselinesrepresentsthei^{th} stamp set and contains two integers, Li and Ri, which represent the inclusive range of the numbers of the stamps available in that set.
1T100
1KM
1N,M2000
1LiRiN
 

 

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum number of different kinds of stamp that Alice could get.
 

 

Sample Input
2 5 3 2 3 4 1 1 1 3 100 2 1 1 50 90 100
 

 

Sample Output
Case #1: 4 Case #2: 50
Hint
In sample case #1, Alice could buy the first and the third stamp sets, which contain the first four kinds of stamp. Note that she gets two copies of stamp 3, but only the number of different kinds of stamps matters, not the number of stamps of each kind. In sample case #2, Alice could buy the first stamp set, which contains 50 different kinds of stamps.
 
题意:给出n个区间,求选k个区间的最大区间并。

思路:可能存在左端点相同的多个区间,那么此时我们肯定选右端点最大的那个区间。现在将区间按左端点排序,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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!