首页 » 技术分享 » D - 渣渣仰慕的爱丽丝 HDU - 6249（背包问题变形)

D - 渣渣仰慕的爱丽丝 HDU - 6249（背包问题变形)

　
评论关闭　614次浏览

爱丽丝喜欢集邮。她现在在邮局买一些新邮票。
世界上有各种各样的邮票;它们的编号是1到N。但是，邮票不是单独出售的;必须成套购买。有M套不同的邮票可供选择;
第i套包括编号从li到ri的邮票 。同一枚邮票可能会出现在不止一套邮票中，而且可能在任何一套邮票中都找不到一枚或多枚邮票。
所有套装的价格都是一样的;因为爱丽丝的预算有限，她最多只能买K套不同的邮票。爱丽丝最多能买到多少种不同的邮票? Input
输入从一行开始，其中包含一个整数T，即测试用例的数量。接下来是T测试用例。
每个测试用例都以一行开始，其中包含三个整数:N、M和K:可用的不同类型邮票的数量、可用邮票集的数量，以及Alice可以购买的最大邮票集数量。
这些行中的第i行表示第i个套邮票，包含两个整数li和ri，表示该套邮票中可用邮票数目的范围。 1≤T≤100 1≤K≤M
1≤N,M≤2000 1≤Li≤Ri≤N Output 对于每个测试用例，输出一行包含“case #x:
y”，其中x是测试用例号(从1开始)，y是Alice可以得到的不同类型邮票的最大数量。

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

思路

链接🔗

代码

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

const int mxn = 2005;
int dp[mxn][mxn];
int a[mxn];

int main()
{
    /* freopen("A.txt","r",stdin); */
    int t, Case = 1;
    scanf("%d", &t);
    while(t --)
    {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        int l, r;
        memset(a, 0, sizeof(a));
        for(int i = 1; i <= m; i ++)
        {
            scanf("%d %d", &l, &r);
            for(int i = l; i <= r; i ++)
                a[i] = max(a[i], r);
        }

        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < k; j ++)
            {
                if(a[i + 1])
                    dp[a[i + 1]][j + 1] = max(dp[a[i + 1]][j + 1], dp[i][j] + a[i + 1] - i);
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
            }
        int ans = 0;
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= k; j ++)
                ans = max(ans, dp[i][j]);
        printf("Case #%d: %d\n", Case ++, ans);
    }


    return 0;
}

代码

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

const int mxn = 2005;
int dp[mxn];
int len[mxn];

int main()
{
    /* freopen("A.txt","r",stdin); */
    int t, Case = 1;
    scanf("%d", &t);
    while(t --)
    {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        int l, r;
        memset(len, 0, sizeof(len));
        for(int i = 1; i <= m; i ++)
        {
            scanf("%d %d", &l, &r);
            for(int j = l; j <= r; j ++)
                len[j] = max(len[j], j - l + 1);
        }

        memset(dp, 0, sizeof(dp));
        while(k --)
        {
            for(int i = n; i >= 1; i --)
                dp[i] = max(dp[i], dp[i - len[i]] + len[i]);
            for(int j = 1; j <=n; j ++)
                dp[j] = max(dp[j], dp[j - 1]);
        }

        printf("Case #%d: %d\n", Case ++, dp[n]);
    }


    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：D - 渣渣仰慕的爱丽丝 HDU - 6249（背包问题变形)，转载请注明来源！

赞 0