题意：给定n个数，要求必须将其中某个数改为P，求改动后最大的区间和可以为多少。
水题。枚举每个区间，如果该区间不修改（即修改该区间以外的数），则就为该区间和，若该区间要修改，因为必须修改，所以肯定是把最小的数修改为P能保证该区间最后和最大，所以比较两种方案的较大者。对于每个区间取出的较大者，再取总共的最大者即可。注意一个trick，枚举到整个区间的时候，是必须要修改一个数的，所以这个最大的这个区间只有一种方案。先预处理1~i的区间和，维护每个区间的最小值和区间和。
#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <string>#include <algorithm>#include <stack>#include <queue>#include <vector>#include <map>#include <set>using namespace std;const int MAX = 1005;const int INF = 1e9;int n;__int64 P, a[MAX];__int64 sum[MAX], smallest[MAX][MAX];void input(){scanf("%d%I64d", &n, &P);for(int i = 1; i <= n; i++)scanf("%I64d", &a[i]);}void solve(){smallest[0][0] = INF;sum[0] = 0;__int64 ans = P;for(int i = 1; i <= n; i++)sum[i] = sum[i – 1] + a[i];for(int i = 1; i <= n; i++){smallest[i][i] = a[i];ans = max(ans, a[i]);for(int j = i + 1; j <= n; j++){smallest[i][j] = min(smallest[i][j – 1], a[j]);ans = max(ans, sum[j] – sum[i – 1] – smallest[i][j] + P);if(i != 1 || j != n)ans = max(ans, sum[j] – sum[i – 1]);}}printf("%I64d\n", ans);}int main(){int T;scanf("%d", &T);while(T–){input();solve();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，友谊之花、爱情之树、以及遗憾之泪！
