专栏文章

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

AA7F3jK9pR0xf_
P14306题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mini9oj4
此快照首次捕获于
2025/12/02 02:51
3 个月前
此快照最后确认于
2025/12/02 02:51
3 个月前
查看原文
感觉不难，赛时 10min 切了。
观察到答案与值域有关，且子序列的下标对答案没有影响，所以我们考虑先排序重构整个序列，再在上面做子序列dp。
状态定义：fif_i 表示以 ii 为结尾的子序列的最大和谐值。
初始化显然是 ∀i∈[1,n],fi=k\forall i\in [1,n],f_i=k
考虑转移，每增加一个长度都会额外产生 kk 的贡献，所以被减数是好算的。关键在于极值如何计算，因为你不知道这个子序列的开头是哪个数。可以找找规律：假设顺序在重构序列中选取两个数 x,yx,y，那么极值为 y−xy-x，如果是三个数 x,y,zx,y,z，那么极值为 z−x=z−y+y−xz-x=z-y+y-x，也就是说加上 ai−aja_i-a_j 就能得到正确的极值。于是我们可以得到转移：
fi=max⁡j<ifj+k−(ai−aj)f_i=\max_{j<i}f_j+k-(a_i-a_j)
直接做是 O(n2)O(n^2) 的，无法通过。
将转移方程拆开，发现与 jj 有关的柿子为 fj+ajf_j+a_j，于是我们开一个变量 O(1)O(1) 维护最大值即可。这样转移的复杂度优化到了 O(1)O(1)，整个 dp 的复杂度为 O(n)O(n)，那么瓶颈在于排序，故时间复杂度为 O(Tnlog⁡n)O(Tn\log n)，可以通过。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...