本题暴力枚举'+','-'操作肯定是不行的，最多有2^99中情况。
定义了：p[101],v[101][20000];
由于n最大100，每个数最大100，所以式子的结果在[-10000,10000]中，所以可以对最终式子的结果进行状态DP。

开v[101][20000],v[i][j]表示前i个数经过几个'+’或'-'后值等于j的状态。
v[i][j]=1或0 ：   
      1表示存在v[i-1][k]!=-1 使得k+p[i]=j;
      0表示存在v[i-1][k]!=-1 使得k-p[i]=j;
这样就用v[i][j]记录了路径。

最后稍加处理即可。
'+' '-' 的操作组合是接近无限的(2^99)，但结果种类是有限的(20000)。这就是我所理解的DP


代码： //M=10000
      v[1][M+p[1]]=1;
      v[2][M+p[1]-p[2]]=0;
      for(int i=3;i<=n;i++)
            for(int j=0;j<=20000;j++)
                   if(v[i-1][j]!=-1)
                   {
                          v[i][j+p[i]]=1;
                          v[i][j-p[i]]=0;
                   }
      for(int i=n,j=T+M;i>=1;i--)
      {
            if(v[i][j]==1)
            {
                 ans[i]=1;
                 j-=p[i];
            }
            else if(v[i][j]==0)
            {
                 ans[i]=0;
                 j+=p[i];
            }
      }

      int m=0;
      for(int i=2;i<=n;i++)
          if(ans[i]==1)
              cout<<i-1-m++<<endl;
      for(int i=2;i<=n;i++)
          if(ans[i]==0)
              cout<<"1"<<endl;

• Re:大彻大悟此题，贴解题思路……（经过仔细思考请进入） (22) longxiaozhi 2011-03-17 06:05:35