题目链接:传送门
题意:
给定一个长度为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; }
本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5194668.html,如需转载请自行联系原作者