题解

39 条题解

  • 2
    @ 2017-10-18 19:21:49

    这不是贪心吗?

    给个例子

    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;
    }
    
  • 0
    @ 2017-05-15 11:43:54

    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]);
    }
    
  • 0
    @ 2015-01-29 12:32:18

    分治(或者叫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;
    }

  • 0
    @ 2009-11-11 18:02:54

    搜索秒杀。。。

  • 0
    @ 2009-11-02 00:01:53

    啊~~~~~~~~~~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);

  • 0
    @ 2009-11-01 14:05:07

    #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

  • 0
    @ 2009-10-19 12:39:59

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-05-14 19:42:25

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

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

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

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

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

    对运算符进行讨论即可。

    所求为max[1][n];

  • 0
    @ 2009-04-01 16:04:28

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

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

  • 0
    @ 2009-03-28 12:37:24

    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]

  • 0
    @ 2008-10-29 13:09:05

    这道题的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;

  • 0
    @ 2008-10-23 19:26:00

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

  • 0
    @ 2008-10-04 15:39:46

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    dp,不简单额,秒杀

  • 0
    @ 2008-09-25 19:08:09

    其实搜索就可以了^^

  • 0
    @ 2008-09-13 15:11:21

    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]

  • 0
    @ 2008-08-13 17:26:51

    O(n^2)?

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

  • 0
    @ 2007-11-12 10:47:53

    O(n^2)

  • 0
    @ 2007-11-10 22:32:03

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2007-10-27 19:12:12

    数据中有0..

    而且必须看成+0

    ...

    我晕倒

  • 0
    @ 2007-10-04 17:41:00

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    晕~花了我一下午的时间

信息

ID
1332
难度
4
分类
动态规划 点击显示
标签
(无)
递交数
284
已通过
118
通过率
42%
上传者