HDU-6249-Alice’s Stamps

ACM模版

描述

题解

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

代码

代码语言：javascript复制

#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: %dn", ce, ans);
    }

    return 0;
}

dp

0 人点赞