273. 分级 - AcWing题库【DP】

273. 分级 - AcWing题库

总结：

1. 对于给定的A序列，第一维肯定是枚举前i个数
2. 第二维，初步想法是以j结尾的最小值，j的范围是1e9范围过大
3. 利用贪心的思路，可以得到：存在一种构造序列B的方案使得所有的B都在A中出现过。
4. 可以将第二维的j变成一个有限的集合即A集合，从而范围缩小了
5. brute force即可，注意到k值的搜寻只进不出用minv维护，减去一维for（k）

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2100;
int f[N][N], a[N], b[N];
int n;
//对于前i个A,以Bj为结尾最小值
//子问题：找到前i-1个A，以Bk为结尾的转移过来  k <= j
int work()
{
    for (int i = 1; i <= n; i ++ ) {
        int minv = INF;
        for (int j = 1; j <= n; j ++ ) {
            minv = min(minv, f[i - 1][j]);
            f[i][j] = minv + abs(b[j] - a[i]);
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; i ++ ) {
        ans = min(ans, f[n][i]);
    }
    return ans;
}

int main(){
    //std::ios::sync_with_stdio(false);
    //std::cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }   
    sort(b + 1, b + n + 1);
    int ans = work();
    reverse(a, a + n);
    ans = min(ans, work());
    return 0;
}