题解：P14306 【MX-J27-T3】旋律

· · 题解

感觉不难，赛时 10min 切了。

观察到答案与值域有关，且子序列的下标对答案没有影响，所以我们考虑先排序重构整个序列，再在上面做子序列dp。

状态定义：f_i 表示以 i 为结尾的子序列的最大和谐值。

初始化显然是 \forall i\in [1,n],f_i=k

考虑转移，每增加一个长度都会额外产生 k 的贡献，所以被减数是好算的。关键在于极值如何计算，因为你不知道这个子序列的开头是哪个数。可以找找规律：假设顺序在重构序列中选取两个数 x,y，那么极值为 y-x，如果是三个数 x,y,z，那么极值为 z-x=z-y+y-x，也就是说加上 a_i-a_j 就能得到正确的极值。于是我们可以得到转移：

f_i=\max_{j<i}f_j+k-(a_i-a_j)

直接做是 O(n^2) 的，无法通过。

将转移方程拆开，发现与 j 有关的柿子为 f_j+a_j，于是我们开一个变量 O(1) 维护最大值即可。这样转移的复杂度优化到了 O(1)，整个 dp 的复杂度为 O(n)，那么瓶颈在于排序，故时间复杂度为 O(Tn\log n)，可以通过。

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 1e5 + 10;
int a[N], n, k;
ll f[N];
il void solve()
{
    cin >> n >> k;
    for(int i = 1;i <= n;++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    ll tmp = 0;
    for(int i = 1;i <= n;++i)
    {
        f[i] = max(1ll * k, tmp + k - a[i]);
        tmp = max(tmp, f[i] + a[i]);
    }
    ll ans = k;
    for(int i = 1;i <= n;++i) ans = max(ans, f[i]);
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int c, t;
    cin >> c >> t;
    while(t--) solve();
    return 0;
}