这不是贪心吗？

给个例子

x为一串正整数数组

那么很显然 -x[1]-x[2]±x[3]±x[4]±...±x[n]的最大值就是-x[1]+x[2]+x[3]+...+x[n]
因为第2个负号后面的数字总可以和第一个负号或者第一个符号+离自己最近的负号（不为第一个负号）的到正值

当然，第1个负号与第2个负号之间的正数会被取成负值，所以需要枚举一遍，取最大值

#include<cstdio>
using namespace std;

int n,tot,ans;
int a[15],sum[15],fsum[15],q[15];

int readln()
{
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}

int max(int x,int y) {return x>y?x:y;}

int main()
{
    n=readln();
    for (int i=1;i<=n;i++)
    {
        a[i]=readln();
        fsum[i]=fsum[i-1];
        if (a[i]<0) {
            sum[i]=sum[i-1]-a[i];
            fsum[i]+=a[i];
            q[++tot]=i;
        }
        else sum[i]=sum[i-1]+a[i];
    }
    ans=sum[n]+2*fsum[n];
    for (int i=tot;i>1;i--) ans=max(ans,sum[n]-2*(sum[q[i]-1]-sum[q[i-1]-1]-fsum[q[i-1]-1]));
    printf("%d",ans);
    return 0;
}

xjb区间dp没什么可以解释的，dp方程有贪心的思想

int Ma[101][101],Mi[101][101],n,a[101];
int main()
{
    scanf("%d",&n);
    For(i,1,n)  For(j,1,n)  Mi[i][j]=1e9,Ma[i][j]=-1e9;
    For(i,1,n)
        scanf("%d",&a[i]),Ma[i][i]=Mi[i][i]=abs(a[i]);

    Dow(i,1,n)
        For(j,i+1,n)
        {
            For(k,i+1,j)
            {
                if(a[k]>=0)
                    Ma[i][j]=max(Ma[i][j],Ma[i][k-1]+Ma[k][j]),
                    Mi[i][j]=min(Mi[i][j],Mi[i][k-1]+Mi[k][j]);
                else 
                    Ma[i][j]=max(Ma[i][j],Ma[i][k-1]-Mi[k][j]),
                    Mi[i][j]=min(Mi[i][j],Mi[i][k-1]-Ma[k][j]);
            }
        }
    printf("%d",Ma[1][n]);
}

分治(或者叫DP?没有用记忆化也差不多掉了)
求出数组中区间0..n-1所能得到的最小值与最大值.
求出所有子区间的最大最小值,推出当前处理区间的最大最小值.

###Block code

int n;
int a[200];

pl DC(int l,int r)
{
if(l==r) return pl(abs(a[l]),abs(a[l]));
pl v(-INF,INF);
for(int i=l;i<r;i++)
{
if(a[i+1]<0)
{
v.first=max(v.first, DC(l,i).first-DC(i+1,r).second );
v.second=min(v.second, DC(l,i).second-DC(i+1,r).first );

}else
{
v.first=max(v.first, DC(l,i).first+DC(i+1,r).first );
v.second=min(v.second, DC(l,i).second+DC(i+1,r).second );
}
}
return v;
}

int main()
{
ios::sync_with_stdio(false);

cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];

cout<<DC(0,n-1).first<<endl;

return 0;
}

搜索秒杀。。。

啊~~~~~~~~~~DP~~~~~~~~~~~

---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

p数组记录符号，a记录绝对值，

f若k=1表示i,j段能构成的最大值，若k=-1表示i,j断的最小值！

f:=max(find(i,h,k)+p[h+1]*find(h+1,j,k*p[h+1]),f);

f:=min(find(i,h,k)+p[h+1]*find(h+1,j,k*p[h+1]),f);

#include

using namespace std;

int main(void)

{

int i,j,t,k,n,a[101],f[101][101][2],b[101];

cin>>n;

for (i=1;i>a[i];

if (a[i]>=0)

b[i]=0;

else

{

b[i]=1;

a[i]=-a[i];

}

f[i][i][0]=f[i][i][1]=a[i];

}

for (t=1;t

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

什么破题目。。。讲就讲清楚。。。

注意。如果第一个是负数。那么相当于第一个数为0(即也能加括号)。

我的算法是O(N^4).

max[i][j]表示区间的最大值。min[i][j]表示区间的最小值。

对于区间[h,t]。f[i],g[i]分别表示前i个数的最大/小值。

对运算符进行讨论即可。

所求为max[1][n];

f第i个位置前有j个左括号和k个右括号时的最大值

(-1)^(j-k)*a[i]是该加上的值，注意初始化只有负数前才可加左括号

Z-Force.Cho

你的程序是错误的

输入

2

-4

5

你会输出－9

动规的话我觉得需要存一个最大和最小值

for i:=1 to n do

begin

read(a[i]);

f1:=a[i]; f2:=a[i];

end;

for l:=2 to n do

for i:=1 to n-l+1 do

begin

j:=i+l-1;

f1:=a[i]+f1;

f2:=a[i]+f2;

//如果a[i]>=0则不需要枚举了，因为在第一个数上加括号毫无意义

if a[i]

这道题的DP方法之所以难想到，很大原因是因为我们不习惯对正负号的操作。数据很弱，搜索完全可以做到0MS。

过程 DFS（T，KUO，HE）；

T表示将要操作的第T个数，KUO表示在T之前已经加了的左括号数，HE表示前T-1个数之和

N个树存储在A数组里

当A[T]>=0时,再加一个左括号与不加左括号对后面的数据无影响..

而当A[T]0时,需要搜索加一个右括号的情况.

代码如下:

if a[t]>=0 then

begin

if kuo>0 then

begin

if kuo mod 2=1 then x:=he+a[t] else x:=he-a[t];

dfs(t+1,kuo-1,x);

end;

if kuo mod 2=0 then x:=he+a[t] else x:=he-a[t];

dfs(t+1,kuo,x);

end

else

begin

if kuo>0 then

begin

if (kuo-1) mod 2=0 then x:=he+a[t] else x:=he-a[t];

dfs(t+1,kuo-1,x);

dfs(t+1,kuo,x);

end;

if kuo mod 2=0 then x:=he+a[t] else x:=he-a[t];

dfs(t+1,kuo,x);

dfs(t+1,kuo+1,x);

end;

DP...想了很长时间。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

dp,不简单额，秒杀

其实搜索就可以了^^

var

n:longint;

a:array[1..10] of longint;

b:array[1..10,1..10] of longint;

Procedure Dp;

var

i,j,k,x:longint;

begin

for i:=n-1 downto 1 do

begin

if a[i]

O(n^2)?

经典O(n^3)....

O(n^2)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

数据中有0..

而且必须看成+0

...

我晕倒

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

晕~花了我一下午的时间