题解：修整土路为单调斜坡（P3666）

一、题目分析

本题要求将给定的海拔序列调整为非递增或非递减序列，使得修改的总成本（各位置绝对差之和）最小。关键信息：

• 输入序列长度$N$（$1 \leq N \leq 2000$）
• 海拔高度$A_i$（$0 \leq A_i \leq 10^9$）
• 目标序列$B$需满足非递增或非递减
• 总成本为$\sum_{i=1}^N |A_i - B_i|$

二、解题思路

1. 问题转化：
   分别求解非递减和非递增序列的最小成本，取较小值。非递增问题可通过反转序列转化为非递减问题。

2. 离散化优化：
   由于$A_i$范围大，将可能的$B_i$值离散化为原始$A_i$的去重排序集合，减少状态数。

3. 动态规划：

   • 状态定义：$dp[0][i][j]$表示前$i$个位置形成非递减序列，第$i$个位置取离散化后第$j$个值的最小成本
   • 状态转移：枚举当前位置的可能值，确保序列单调性

三、代码解析

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

const int INF = 0x3f3f3f3f;
int dp[2][2333][2333];  // dp[0]:非递减，dp[1]:非递增
int a[2333];            // 原始海拔序列
int b[2333];            // 离散化后的序列
map<int, int> mp;       // 离散化映射

int main() {
    int n;
    scanf("%d", &n);
    
    // 读取原始海拔序列
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    
    // 离散化：去重排序
    sort(b, b + n);
    int id = -1;
    for (int i = 0; i < n; ++i) {
        if (i == 0 || b[i] != b[i-1]) {
            id++;
            b[id] = b[i];
            mp[b[i]] = id;  // 记录值对应的离散化索引
        }
    }
    
    // 初始化：第一个位置的所有可能值
    memset(dp, INF, sizeof(dp));
    for (int i = 0; i <= id; ++i) {
        dp[0][0][i] = dp[1][0][i] = abs(a[0] - b[i]);
        if (i > 0) {
            // 优化：取更优的前一个状态
            dp[0][0][i] = min(dp[0][0][i], dp[0][0][i-1]);
            dp[1][0][i-1] = min(dp[1][0][i-1], dp[1][0][i]);
        }
    }
    
    // 动态规划求解非递减和非递增序列
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j <= id; ++j) {
            // 非递减序列：当前值≥前一个值
            dp[0][i][j] = dp[0][i-1][j] + abs(a[i] - b[j]);
            if (j > 0) dp[0][i][j] = min(dp[0][i][j], dp[0][i][j-1]);
            
            // 非递增序列：当前值≤前一个值（通过反转序列转化）
            dp[1][i][j] = dp[1][i-1][j] + abs(a[i] - b[j]);
            if (j > 0) dp[1][i][j-1] = min(dp[1][i][j-1], dp[1][i][j]);
        }
    }
    
    // 取非递减和非递增的最小成本
    printf("%d\n", min(dp[0][n-1][id], dp[1][n-1][0]));
    
    return 0;
}

四、关键步骤解析

1. 离散化处理：

   • 将原始序列$a$复制到$b$并排序去重，得到离散化后的可能值集合
   • 映射$mp$记录每个值对应的索引，将$B_i$的可能取值压缩到$O(N)$范围

2. 状态定义：

   • $dp[0][i][j]$：前$i$个位置形成非递减序列，第$i$个位置取$b[j]$的最小成本
   • $dp[1][i][j]$：前$i$个位置形成非递增序列，第$i$个位置取$b[j]$的最小成本

3. 状态转移：

   • 非递减序列：当前值$b[j]$需≥前一个位置的可能值，取所有$k \leq j$中的最小值
   • 非递增序列：通过反转序列转化为非递减问题，当前值$b[j]$需≤前一个位置的可能值

4. 初始化与优化：

   • 第一个位置的成本为$|a[0]-b[j]|$
   • 利用前缀最小值优化，避免重复计算

五、示例解析

输入：

7
1
3
2
4
5
3
9

1. 离散化后序列：
   原始序列去重排序后为$[1,2,3,4,5,9]$，对应索引0~5。

2. 动态规划过程：

   • 非递减序列最优解：$[1,3,3,4,5,5,9]$
     成本为$|2-3| + |3-5| = 3$
   • 非递增序列需反转原序列后计算，最终取两者最小值3。

六、复杂度分析

• 时间复杂度：$O(N^2 \log N)$
  离散化排序$O(N \log N)$，动态规划$O(N^2)$
• 空间复杂度：$O(N^2)$
  存储动态规划数组和离散化序列

七、注意事项

1. 离散化必要性：
   若不离散化，$A_i$可达$10^9$，无法直接存储所有可能的$B_i$值。

2. 非递增处理：
   代码中通过状态转移逻辑隐式处理非递增，实际也可反转序列后求解非递减问题。

3. 前缀优化：
   $dp[0][i][j] = min(dp[0][i][j], dp[0][i][j-1])$利用前缀最小值，避免重复比较前序状态。

八、优化方向

1. 滚动数组优化：
   观察到$dp[i]$仅依赖$dp[i-1]$，可使用滚动数组将空间复杂度降为$O(N)$。

2. 二分答案优化：
   对于非递减序列，可结合二分查找确定当前位置的最小成本，进一步降低时间复杂度。

3. 中位数性质：
   当序列长度固定时，最优$B_i$可能与原始序列的中位数相关，可用于初始化或剪枝。