http://acm.neu.
题目大意：n个数（只为0,1,2），按顺序分成m组，使得所有组的积加起来最大。

思路应该是动规，用f[i,j]表示前i个数分成j组的最大值，枚举第j组从k到i，则f[i,j]=Max(f[k-1,j-1]+(k--i的乘积)) (k>=j),下面是我的程序，wa到暴

#include <stdio.h>
#include <stdlib.h>

long long f[55][55],tpow[55],tmp;

int zero[55],one[55],two[55],n,m,a[55],i,j,k;

int main()
{
    tpow[0]=1;
    for (i=1; i<=50; i++) tpow[i]=tpow[i-1]*2;       //预处理出2的阶乘和，这样求k--i个数的乘积可以直接由其中2的个数得到
    while (scanf("%d%d",&n,&m),n!=0)
    {
          zero[0]=0; one[0]=0; two[0]=0;
          for (i=1; i<=n; i++) 
          {   
              scanf("%d",a+i);
              zero[i]=zero[i-1]; one[i]=one[i-1]; two[i]=two[i-1];
              if (a[i]==0) zero[i]++; else
              if (a[i]==1) one[i]++; else two[i]++;
          }
          memset(f,0,sizeof(f));
          for (i=1; i<=n; i++)
          {
            if (zero[i]==0) f[i][1]=tpow[two[i]]; else f[i][1]=0;      //先直接求出f[i][1]
            for (j=2; j<=m; j++) 
            {
                if (j>i) break;
                for (k=j; k<=i; k++)           //对f[i][j]开始枚举动规，由于剩下k-1个数分成j-1组，克制k>=j
                {
                    if (zero[k-1]==zero[i]) tmp=tpow[two[i]-two[k-1]]; else tmp=0;
                    if (f[i][j]<f[k-1][j-1]+tmp) f[i][j]=f[k-1][j-1]+tmp;
                }
            }
          }
          printf("%lld\n",f[n][m]);
    }
    return 0;
}

不是，要是有测试数据的话就没这么纠结了...蛋疼

而且你的程序没看大懂，能不能稍微讲一下算法？

还是没解决。。想不通为什么会WA

看了你的代码，思路应该差不多，用f[i,k,j]表示在 k-j中插入i个分割，所以f[m-1,0,n-1]就是答案。

然后我生成了大量个随机数据，每次生成500个，然后用你我的程序输出结果对比，试了10次。。然后发现都是一样的

纠结啊。但我觉得你的程序应该是还可以优化的，现在的时间复杂度偏大，只不过这个数据不是很大

经对比测试，我的程序在求k--j段的乘积有错误（虽然这个实现很简单，但我还真找不到，难道是当局者迷...)，换成你的方法就ac了，感觉还真有点诡异、、、

还有一个下标的问题，c语言中数组一般以0为下标，但我最初学的是pascal语言，所以习惯了用1做下表，虽然有时候会尽量去适用0做下标，但一遇到复杂点的问题就感觉还是用1做下标比较舒服，不知道这种编程习惯好不好。。

不过非常感谢了，难的这么上心，一起进步

我姓曹，叫我小曹好了，今年大二，不过我不是计算机专业的，学这个只是兴趣，下学期报了计算机二专，可以系统得学习了

这题我没想到很精妙的方法，只能硬算：

首先由
(n+1)^3-n^3==3*n*n+3*n+1
n^3-(n-1)^3==3*(n-1)*(n-1)+3*(n-1)+1
.
.
.
2^3-1^3==3*1*1+3*1+1

上面n个式子相加，可以得到公式:1^2+2^2+3^2.......n^2==1/6*n*(n+1)*(2n+1)

然后上面直接得到公式=1/2*SUM(k^2+k)   (1<=k<=n)

将上面那个公式套进去，最后结果应该是1/6*n*(n+1)*(n+2)

今天晚上再想想看有没有巧妙一点的方法吧

有一个看起来漂亮一点的证明的了：

有1+2+3+...n=C(n+1,2)
所以上式=C(2,2)+C(3,2)+C(4,2)+....C(n+1,2)
        =C(3,3)+C(3,2)+C(4,2)+....C(n+1,2)
        =C(4,3)+C(4,2)+......C(n+1,2)
        =C(5,3)+........C(n+1,2)
        =C(n+2,3)

这个公式怎么从几何角度推导啊？我几何一向不大好，比较偏爱代数