[NOIP2023] 天天爱打卡

题目描述

小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。

开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 \(n\) 天，编号为从 \(1\) 到 \(n\)。

对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 \(d\)。初始时，他的能量值是 \(0\)，并且试运行期间他的能量值可以是负数。

而且大 Y 不会连续跑步打卡超过 \(k\) 天；即不能存在 \(1\le x\le n-k\)，使得他在第 \(x\) 到第 \(x+k\) 天均进行了跑步打卡。

小 T 同学在软件中设计了 \(m\) 个挑战，第 \(i\)（\(1\le i \le m\)）个挑战可以用三个正整数 \((x_i,y_i,v_i)\) 描述，表示如果在第 \(x_i\) 天时，用户已经连续跑步打卡至少 \(y_i\) 天（即第 \(x_i-y_i+1\) 到第 \(x_i\) 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 \(v_i\)。

现在大 Y 想知道，在软件试运行的 \(n\) 天结束后，他的能量值最高可以达到多少？

输入格式

本题的测试点包含有多组测试数据。

输入的第一行包含两个整数 \(c\) 和 \(t\)，分别表示测试点编号和测试数据组数。对于样例，\(c\) 表示该样例与测试点 \(c\) 拥有相同的限制条件。

接下来，对于每组测试数据：

• 输入的第一行包含四个正整数 \(n,m,k,d\)，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
• 接下来 \(m\) 行，每行包含三个正整数 \(x_i,y_i,v_i\)，表示一次挑战。

输出格式

输出一行一个整数表示对应的答案。

样例 #1

样例输入 #1

1 1
3 2 2 1
2 2 4
3 2 3

样例输出 #1

2

提示

【样例解释 #1】

在第 \(1,2\) 天跑步打卡，第 \(3\) 天不跑步打卡，最终会获得 \((-1)+(-1)+4=2\) 的能量值。

【样例解释 #2】

该组样例满足测试点 \(3\) 的条件。

【样例解释 #3】

该组样例满足测试点 \(5\) 的条件。

【样例解释 #4】

该组样例满足测试点 \(15\) 的条件。

【样例解释 #5】

该组样例满足测试点 \(17\) 的条件。

【样例解释 #6】

该组样例满足测试点 \(19\) 的条件。

【数据范围】

记 \(l_i=x_i-y_i+1\)，\(r_i=x_i\)​；

对于所有测试数据，保证：\(1\le t\le 10\)，\(1\le k\le n\le 10^9\)，\(1\le m\le 10^5\)，\(1\le l_i\le r_i\le n\)，\(1\le d,v_i\le 10^9\)。

特殊性质 A：\(k\le 10^2\)；

特殊性质 B：\(\forall 1\le i<m\)，\(r_i<l_{i+1}\)；

特殊性质 C：\(\forall 1\le i<j\le m\)，\(l_i<l_j\)，\(r_i<r_j\)。

36分的题解

这个题，36分，看起来就比较好写，但是因为我理解错题意，导致错了很久，在这里说明一下，这个时候突然想起来，学生和我说读错题导致一直过不了的问题，我还有一些不理解，现在终于理解了：一、奖励的部分会有重复的，比如说第2天连续运动3天，可能会有7的奖励，也可能会有8的奖励，我当时取的是最大值，其实最后取的是和；二、如果第i天连续运动了3天，连续运动了4天，那么这些奖励都会加起来，而不是最后取一个最大值。

第一个想法是：

\(dp[i][j]表示前i天已经连续运动了j天获得的最大收益, 但是我转念一想，这个dp如何转移？ dp[i][j]=max(dp[i-j][0]-d*(i-j+1))\)，显然这个是不用转移的，直接等于就行了，所以我当时放弃了这个想法

第二个想法：

\(dp[i]表示前i天获得的最大收益，但是这个我无法知道运动情况，如果dp[i]=dp[i-j]-d*(i-j+1)，这样有个问题出现了，就是我已经连续运动了i-j+1天，但是dp[i-j]的部分仍然可以连续运动，那么这样连续运动的天数就会超过题目的限制K，而且我也无法知道连续运动的天数，不能判断，这时候我想到了既然不能标记第i天是否运动了，所以我可以后面标记[0/1]表示第i天是否运动了，但是我马上否定了自己，因为我经常这个干，往往这么做都错了，所以没有继续往深了想，事实证明这次没准对了，我看见题解里有这样的DP设置\)

第三个想法：

\(回到了第一个dp表示法，dp[i][j]表示前i天已经连续运动了j天获得的最大收益,如何更新他呢？我把j这个区间分成两部分，dp[i][ss]和dp[i-ss][j-ss],用这两个值加起来，但是一直过不了，我看了一下题解发现dp[i][j]可以通过dp[i-1][j-1]-d转移，修改了之后就可以了，但是我一直想不到上面的DP转移到底有什么问题？问题在于长度为j-ss和ss两端结合起来，这样的想法是错误的，比如说求dp[5][2]，他应该是4[1]和5[1]合成的，但是5[1]的值建立在4[0]的基础之上，所以他并不能和4[1]合并\)