传送门：HDU5280

【题意】某天学姐姐得到了一个数组A，在这个数组的所有非空区间中，她找出了一个区间和最大的，并把这个区间和定义为这个数组的美丽值。

但是她觉得这个数组不够美，于是决定修理一下这个数组。

学姐姐将会进行一次操作，把原数组中的某个数修改为P（必须修改）。

最后她想使得修改后的数组尽可能美丽。请你帮助她计算经过修理后，这个数组的美丽值最大能是多少？

【分析】最容易想到的是暴力枚举子串起点终点，然后找到这区间的最小值，分别取下替换p或者不替换的值，需要注意区间[1,n]是必须替换的，然后线段树维护区间会超时，我用了ST维护。这样复杂度n^2+n*logn.

【AC CODE】234ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN = 1000+10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL a[MAXN],sum[MAXN];

LL dp[MAXN][30];
void st_init(int n)
{
    repe(i,1,n) dp[i][0] = a[i];
    for(int j = 1; (1<<j) <= n; j++)
    {
        for(int i = 1; i+(1<<j)-1 <= n; i++)
            dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
    }
}
int query(int x, int y)
{
    int k = 0;
    while((1<<(k+1)) <= y-x+1) k++;
    return min(dp[x][k], dp[y-(1<<k)+1][k]);
}

int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n,p;
        scanf("%d %d", &n, &p);
        repe(i,1,n)
        {
            scanf("%I64d", &a[i]);
            sum[i] = sum[i-1]+a[i];
        }
        st_init(n);
        LL mx = -INF;
        repe(st,1,n)
        {
            repe(ed,st,n)
            {
                mx = max(mx,sum[ed]-sum[st-1]-query(st,ed)+p);
                if(ed-st+1 != n)
                    mx = max(mx,sum[ed]-sum[st-1]);
            }
        }
        printf("%I64d\n", mx);
    }
    return 0;
}

 

当然还有一种O(n)的做法,分别维护从左到右以及从右到左的最大连续子序列以及她来自那个起点，则枚举替换的位置，则包含他的区间的最值为dpl[i]+dpr[i+1],都取一下是否把a[i]替换成p，还是注意区间[1,n]必须替换。这样复杂度O(n)

【AC CODE】15ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int MAXN = 1000+10;
const LL INF = 0x3f3f3f3f3f3f3f3f;
LL a[MAXN],dpl[MAXN],dpr[MAXN];
int st[MAXN],ed[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n,p;
		scanf("%d %d", &n, &p);
		repe(i,1,n)
			scanf("%I64d", &a[i]);
		st[0] = 1;
		repe(i,1,n)
		{
			if(dpl[i-1]+a[i] > a[i])
			{
				dpl[i] = dpl[i-1]+a[i];
				st[i] = st[i-1];
			}
			else
			{
				dpl[i] = a[i];
				st[i] = i;
			}
		}
		dpr[n+1] = 0;ed[n+1] = n;
		per(i,n,1)
		{
			if(dpr[i+1]+a[i] > a[i])
			{
				dpr[i] = dpr[i+1]+a[i];
				ed[i] = ed[i+1];
			}
			else
			{
				dpr[i] = a[i];
				ed[i] = i;
			}
		}
		LL ans = -INF;
		repe(i,1,n)
		{
			ans = max(ans,dpl[i]+dpr[i+1]-a[i]+p);
			if(ed[i]-st[i]+1 != n)
				ans = max(ans,dpl[i]+dpr[i+1]);
		}
		printf("%I64d\n", ans);
	}
	return 0;
}