区间DP || HDU 6249 Alice’s Stamps

题意：标号为1-n的n种邮票，m个邮票集，每个集里有标号从Li到Ri的邮票，要从中选K个邮票集，使这K个邮票集能覆盖最多种的邮票，问最多能覆盖多少种邮票

思路：区间DP （我：？？？

f[i][j]表示从1 - i 位置选择 j 个集合的覆盖种数

首先它可以从f[i][j] = max(f[i][j], max(f[i-1][j], f[i][j-1]))转移来

其次考虑它能转移到的点

用up[i] 记录覆盖i点的线段最右的点，如果要在 i 后面加一条线段，那么肯定优先取这个（因为它最右，同样加一条线段得到的覆盖长度更长

所以f[i][j]可以转移到f[up[i]][j], if(up[i]) f[up[i]][j] = max(f[i-1][j-1]+up[i]-i+1, f[up[i]][j]);

嘤嘤嘤的哭了

区间DP的话，把区间排个序，然后去掉有完全包含的区间~

#include <map>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long LL;

const int maxn = ;

const int maxm = ;

struct node

{

    int l, r;

}a[maxn];

bool cmp(node x, node y)

{

    if(x.l != y.l) return x.l<y.l;

    return x.r<y.r;

}

int up[maxn], f[maxn][maxn];

int main()

{

    int T, tt=;

    scanf("%d", &T);

    while(T--)

    {

        int n, m, k;

        scanf("%d%d%d", &n, &m, &k);

        memset(up, , sizeof(up));

        memset(f, , sizeof(f));

        for(int i = ; i <= m; i++)

        {

            scanf("%d%d", &a[i].l, &a[i].r);

            for(int j = a[i].l; j <= a[i].r; j++)

                up[j] = max(up[j], a[i].r);

        }

        sort(a+, a++m, cmp);

        for(int i = ; i <= n; i++)

        {

            for(int j = ; j <= k; j++)

            {

                f[i][j] = max(f[i][j], max(f[i-][j], f[i][j-]));

                if(up[i]) f[up[i]][j] = max(f[up[i]][j], f[i-][j-]+up[i]-i+);

            }

        }

        /*for(int i = 1; i <= n; i++)

            for(int j = 1; j <= k; j++)

                printf("f[%d][%d] = %d\n", i, j, f[i][j]);*/

        printf("Case #%d: %d\n", ++tt, f[n][k]);

    }

    return ;

}

巴特西

区间DP || HDU 6249 Alice’s Stamps

最新文章

热门文章