2022ICPC 网络赛第二场 B Non-decreasing Array（区间dp）

You are given a non-decreasing array of integers a1​,a2​,…,an​. In one operation, when the current length of the array is m:

• Firstly you can choose an index i(1
• Secondly you can choose an index i(1

You should ensure that the array is non-decreasing after every delete or change.

Now you want to know that after operating k(1≤k≤n) times, when the current length of the array is m, what is the maximum value of ∑m  i=2   ​(ai​−ai−1​)^2.

You need to answer for each k(1≤k≤n), different queries are independent of each other.

输入格式:

The first line contains one integer n(3≤n≤100).

The second line contains n integers a1​,a2​,...,an​(−10^9≤ai​≤10^9).

输出格式:

Output n lines, each of which contains a single integer—the i-th number is for the answer of k=i.

输入样例:

5
1 2 3 4 5

输出样例:

10
16
16
16
16

类似于石子合并题    两次操作可以看作两次删除（修改、删除）。那么最多删除n-2个 ， 操作次数k最多为(n-2)/2

使得题目要求的值最大的方法就是删除  除头尾之外的所有值 

#include 
#include 
using namespace std;
typedef long long ll;
const int N = 110;
int n , m , res;
int a[N] , f[N][N];//到第i个数的位置 删除了j个 ， 保留第一个和最后一个
int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i++ ){
        cin >>a[i] ;
    }
    for(int i = 1; i <= n ;i++){ //到i位置时
        for(int j = 0 ; j <= i - 2 ; j++){//删除j个数时
            for(int k = 0 ; k <= j ; k++){
                int pos = i-k-1;//i位置的前一个未删除的元素
                f[i][j] = max( f[i][j] , f[pos][j-k] + (a[i]-a[pos])*(a[i]-a[pos]) ) ;
            }
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if( i * 2 > n - 2 ) cout << f[n][n-2] << '\n';
        else cout << f[n][2 * i] << '\n';
    }
 
    return 0;
}