USACO08FEB Making the Grade G

题目链接

Solution

可以发现当前状态只与当前的位置和当前修改后的值有关。如果按照单调不降序列 dp：

设 (f_{i,j}) 表示当前走到第 (i) 条路，修改后的值是 (j) 能得到的最小代价。那么有一个简单的转移方程式：

[f_{i,j}=max(f_{i-1,k})+|a_i-j|(k≤j) ]

再一看数据范围：(a_i≤10^9)...

考虑一个性质：因为每个位置进行 (1) 单位的修改代价都是一样的，那么每个数修改后的值只可能是原数列中存在的值。根据这一点，可以对数列进行离散化，能成功地把空间复杂度压缩到了 (O(n^2))。

现在 dp 的时间复杂度依然是 (O(n^3))，有一个简单的优化，就是对 (i) 记一个前缀最大值 (g_{i,j})：

[g_{i,j}=max(f_{i,k}) (k≤j) ]

它的转移方程式是这样的：

[g_{i,j}=max(g_{i,j-1},f_{i,j}) ]

这样做之后时间复杂度也变成了 (O(n^2))。

不上升序列就把 (a_i) 反过来再 dp 一遍。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;

const int N = 2333;
LL n, tmp, ans = 1e18, a[N], b[N], c[N], f[N][N], g[N][N];

void dp()
{
    memset(f, 0x7f7f7f, sizeof(f));
    memset(g, 0x7f7f7f, sizeof(g));
    for(int i = 1; i <= tmp; i++) f[0][i] = g[0][i] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= tmp; j++)
            f[i][j] = min(f[i][j], g[i - 1][j] + abs(b[a[i]] - b[j]));
        for(int j = 1; j <= tmp; j++)
            g[i][j] = min(f[i][j], g[i][j - 1]);
    }
    for(int i = 1; i <= tmp; i++) ans = min(ans, f[n][i]);
    return ;
}

int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), b[i] = a[i];
    sort(b + 1, b + n + 1);
    tmp = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + tmp + 1, a[i]) - b;
    for(int i = 1; i <= n; i++) c[i] = a[i];
    dp();
    for(int i = 1; i <= n; i++) a[i] = c[n - i + 1];
    dp();
    printf("%lld", ans);
    return 0;
}