HDU5280 Senior's Array(简单DP)

时间:2022-01-26 18:32:32

题目链接:

pid=5280">传送门

题意:

给定一个长度为n的序列,和一个改动的值p,必须从原序列中选一个位置改动成p,

求改动后的区间和的最大值。

分析:

枚举位置+最大区间和。

复杂度O(n^2);

代码例如以下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std; typedef long long LL; const int maxn = 1010; const LL inf = 1e15+10; LL a[maxn],b[maxn];
LL dp[maxn]; int main()
{
int t,n,p;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&p);
for(int i=0;i<n;i++) scanf("%I64d",a+i);
LL ans = -inf;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(j==i) b[j]=p;
else b[j]=a[j];
dp[j]=b[j];
}
for(int j=1;j<n;j++){
dp[j]=max(dp[j-1]+b[j],dp[j]);
ans=max(ans,dp[j]);
}
}
printf("%I64d\n",ans);
}
return 0;
}