【DP】The 2022 ICPC Asia Regionals Online Contest (II) B Non-decreasing Array

超、凢脫俗 2024-03-22 21:38 41阅读 0赞

[PTA | 程序设计类实验辅助教学平台][PTA _]

题意：

给定一个不下降的序列，每次操作有两步：

1.选择2~N的一个数，删除这个数

2.选择2~N的一个数，改变这个数为任意值

要满足该数列不下降，N-2次询问，问操作i次之后

![f7ba1cd7b28246e2ad38b0ce1ee4e3ab.png][]

最大

![c1de0a5e9a6f42b9a934770226d21f42.png][]

思路：

首先有个结论：改变一个数等效于删除这个数

![52eee7f4b53f4a6fa92947dc7f998d4b.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e2+10;
    const int mxv=1e2+10;
    const int mod=1e9+7;
    
    int N;
    int a[mxn];
    int dp[mxn][mxn];
    
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=2;i<=N;i++){
    		for(int j=0;j<=i-2;j++){
    			for(int k=0;k<=j;k++){
    				dp[i][j]=max(dp[i][j],dp[i-k-1][j-k]+(a[i]-a[i-k-1])*(a[i]-a[i-k-1]));
    			}
    		}
    	}
    	for(int i=1;i<=N;i++){
    		if(i*2<=N-2) cout<<dp[N][i*2]<<'\n';
    		else cout<<dp[N][N-2]<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[PTA _]: https://pintia.cn/problem-sets/1574060137151397888/exam/problems/1574060247893606401?type=7&page=0
[f7ba1cd7b28246e2ad38b0ce1ee4e3ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/edee374110844eff8d069b2b633b6469.png
[c1de0a5e9a6f42b9a934770226d21f42.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0987d15b149f43d48b46439fb66d21f6.png
[52eee7f4b53f4a6fa92947dc7f998d4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d2a8d907a7704848b3b651d76dba212c.png