给定n个数字的序列,对位置i进行一次操作将使得都变成
特别的,对位置0进行操作将使得和都变成
对位置n-1进行操作将使得和都变成
并且操作过位置i之后,位置0到i都不能再操作设最多可以操作次,最后得到的整个序列的总和最大可以是
你需要求出
给定n个数字的序列,对位置i进行一次操作将使得都变成
5,[1,2,3,4,5]
[18,21,22,22,22]
输入:n=5, 输入序列为[1,2,3,4,5][1,2,3,4,5]对应位置0,1,2,3,4只能操作1次的时候,对位置1操作得到[3,3,3,4,5],或者对位置2操作可以得到[1,4,4,4,5],或者对位置3操作可以得到[1,2,5,5,5],都可以得只能操作2次的时候,按次序操作位置1和位置3可以得到[3,3,5,5,5],其他操作不会得到更优的结果,所以能操作3次以上的时候可以得到的最优序列为[3,4,5,5,5](依次操作位置1,位置2,位置3),所以
class Solution { public: /** * * @param n int整型 数字个数 * @param a int整型vector 待操作序列 * @return int整型vector */ vector<int> ans; struct Sta{ int pos, k, mx; }; vector<int> solve(int n, vector<int>& a) { // write code here ans.resize(n, INT_MIN); int maxe = *max_element(a.begin(), a.end()); vector<vector<int>> dp(201, vector<int>(201, -1)), dp1 = dp; queue<Sta> q; int sum = 0; for(int i = 0; i < n; ++i){ sum += a[i]; int t = a[i], g = a[i], cnt = 1; if(i > 0) t= max(a[i-1], t), g += a[i-1],cnt++; if(i < n - 1) t =max(a[i+1], t), g += a[i+1], cnt++; q.push({i, 1, t}); dp[i][t]=max(dp[i][t], cnt*t-g); ans[0] = max(cnt*t-g, ans[0]); } for(int k = 1; k < n; ++k){ int sz = q.size(); for(int i = 0; i < sz; ++i){ auto sta = q.front(); q.pop(); int pos = sta.pos, kk = sta.k, mx = sta.mx; for(int j = pos+1; j < n; ++j){ int w, g, cnt = 2;//扩展状态 if(j == pos+1) w = mx, g = 2*mx; else if(j == pos+2) w = max(mx, a[j]), g = mx+a[j]; else w = max(a[j-1],a[j]), g = a[j-1]+a[j]; if(j < n - 1) w = max(a[j+1], w), g += a[j+1], cnt++; if(dp1[j][w]==-1) q.push(Sta{j, kk+1, w});//保存状态 dp1[j][w]=max(dp1[j][w], cnt*w-g+dp[pos][mx]);//更新结果 ans[kk] = max(dp1[j][w], ans[kk]); } dp[pos][mx] = -1;//还原数组为-1,方便下一轮扩展用 } swap(dp, dp1); } for(auto &x : ans) x+=sum; return ans; } };
class Solution { public: vector<int> solve(int n, vector<int>& a) { int maxValue=0; vector<int>res; for(int i=0;i<n;i++) { maxValue=max(maxValue,a[i]); } vector<vector<vector<vector<int>>>>dp(n,vector<vector<vector<int>> >(n+1,vector<vector<int>>(2,vector<int>(maxValue+1,-1)))); for(int i=0;i<n;i++) for(int j=0;j<=i+1;j++) { if(i==0) { int t; if(j==0) dp[i][j][0][a[i]]=a[i]; if(j==1) { t=max(a[i],a[i+1]); dp[i][j][1][t]=t; } } else { for(int k=0;k<=maxValue;k++) { int t; if(dp[i-1][j][0][k]!=-1) { dp[i][j][0][a[i]]=max(dp[i][j][0][a[i]],dp[i-1][j][0][k]+a[i]); } if(dp[i-1][j][1][k]!=-1) { //前一项操纵做了,本项不操作,则a[i]与a[i-1]元素一样 dp[i][j][0][k]=max(dp[i][j][0][k],dp[i-1][j][1][k]+k); } if(j>=1&&dp[i-1][j-1][0][k]!=-1) { //前一项没有放,但是这一项要放,取a[i-1],a[i],a[i+1]的最大值 t=max(k,a[i]); if(i+1<n) t=max(t,a[i+1]); dp[i][j][1][t]=max(dp[i][j][1][t],dp[i-1][j-1][0][k]-k+2*t); } if(j>=1&&dp[i-1][j-1][1][k]!=-1) { t=max(k,a[i]); if(i+1<n) t=max(t,a[i+1]); dp[i][j][1][t]=max(dp[i][j][1][t],dp[i-1][j-1][1][k]-k+2*t); } } } } int num; for(int j=1;j<=n;j++) { num=0; for(int k=0;k<=maxValue;k++) { if(dp[n-1][j][0][k]!=-1) num=max(num,dp[n-1][j][0][k]); if(dp[n-1][j][1][k]!=-1) num=max(num,dp[n-1][j][1][k]); } res.push_back(num); } return res; } };