专栏首页ACM小冰成长之路HDU-6249-Alice’s Stamps

HDU-6249-Alice’s Stamps

ACM模版

描述

题解

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

代码

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-5534-Partial Tree

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <algor...

    f_zyj
  • POJ-3866-Exclusive Access 2

    ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

    f_zyj
  • HDU-5985-Lucky Coins

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <cstri...

    f_zyj
  • P2331 [SCOI2005]最大子矩阵

    题目描述 这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵不能相互重叠。 输入输出格式 输入格式: 第一行...

    attack
  • P1880 石子合并

    题目描述 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。 试...

    attack
  • HDU 5636 Shortest Path(Floyed,枚举)

    Shortest Path Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131...

    ShenduCC
  • Backpack problem

    AngelNH
  • 2559. [NOIP2016]组合数问题

    【题目描述】 【输入格式】    从文件中读入数据。    第一行有两个整数t, k,其中t代表该测试点总共有多少组测试数据,k的意义见【问题描述】。 ...

    attack
  • 93. [NOIP2001] 数的划分

    问题描述 将整数n分成k份,且每份不能为空,任意两种方案不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; ...

    attack
  • 单调队列,单调栈总结

    最近几天接触了单调队列,还接触了单调栈,就总结一下。 其实单调队列,和单调栈都是差不多的数据类型,顾名思义就是在栈和队列上加上单调,单调递增或者单调递减。当...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券