ACM模版

描述

题解

DP 问题，设 dp[i][j] 表示前 i 个位置选取 j 个区间的最优解。当然 i 要加以处理，因为我们需要 i 是某个区间的右端点，这样选取区间才完整，具体的处理方法也很容易理解，直接看代码吧~~~

代码

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 2005;

int dp[MAXN][MAXN];
int t[MAXN];

int main()
{
    int T;
    scanf("%d", &T);

    for (int ce = 1; ce <= T; ce++)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);

        int x, y;
        memset(t, 0, sizeof(t));
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d", &x, &y);
            for (int i = x; i <= y; i++)
            {
                t[i] = max(t[i], y);
            }
        }

        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < k; j++)
            {
                if (t[i + 1])
                {
                    dp[t[i + 1]][j + 1] = max(dp[i][j] + t[i + 1] - i, dp[t[i + 1]][j + 1]);
                }
                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", ce, ans);
    }

    return 0;
}

我的博客即将同步至腾讯云+社区，邀请大家一同入驻！！！