ICPC2022网络赛第二场

B Non-decreasing Array 暴力动态规划

推荐一个大佬的博客：大佬的讲解

题意

emm，大家来看题解应该都明白题意，就不写了。

思路（区间dp）

f [ i ] [ j ] f[i][j] f[i][j]的两个状态分别表示为从开头到以 i i i 为结尾的删除 j j j 个数的最大值。所以我们就可以得出最后的结果就是 f [ n ] [ p o s ] f[n][pos] f[n][pos]，pos的值后面会说。
首先我们怎么找出所有的以 i i i 结尾的所有的情况呢？这时候我们可以在纸上画一下：

通过不断调整起点的位置（ i i i 的位置是终点）就可以得到所有的情况了。具体的 *** 作就是不断改变k的长度。长度里面的全部删除需要k次 *** 作，我们一共要删除j次，所以就是:

f [ i − k − 1 ] [ j − k ] + ( a [ r ] − a [ l ] ) ∗ ( a [ r ] − a [ l ] ) ; f[i - k - 1][j - k] + (a[r] - a[l]) * (a[r] - a[l]); f[i−k−1][j−k]+(a[r]−a[l])∗(a[r]−a[l]);

最后在结果上我们要观察结果的情况，我们可以得到删除一次但是跨越的距离是2，比如：

	1 2 3 4 5，第一次的 *** 作是 1 2 5 5，删掉3，把4变成5，所以就相当于
1 2 5，删掉了两个数的最大值的情况。

代码：

#include 

using namespace std;

const int N = 111;
#define int long long

int n;
int a[N];
int f[N][N]; // 第i位 删除j次 但是保留i位置 的最大值

int calc(int l, int r) {
    return (a[r] - a[l]) * (a[r] - a[l]);
}

signed main() 
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for(int i = 1; i <= n; i ++ ) 
        for(int j = 0; j <= i - 2; j ++ ) // 删除多少个数，小于等于2就是开头和结尾不能删除
            for(int k = 0; k <= j; k ++ ) 
            {
                int pos = i - k - 1; // 删除[pos + 1, i - 1]的区间:[i - k + 1, i - 1] // k是长度
                f[i][j] = max(f[i][j], f[pos][j - k] + calc(pos, i));
            }
    
    for(int i = 1; i <= n; i ++ ) 
    {
        // 因为能过 *** 作两次所以删除乘2，就是删除1次但我可以用距离为2的数字，2次就是距离为4
        if(i * 2 > n - 2) cout << f[n][n - 2] << endl;
        else cout << f[n][2 * i] << endl;
    }
    return 0;
}