九度教程第100題

C語言源碼： [cpp]  #include<stdio.h>   #include<limits.h>   #define maxsize 4010   #define size 2000   int dp[110][maxsize];   int max2(int a,int b)   {       return a>b?a:b;   }   int max(int a,int b,int c)   {       return max2(a,b)>c?max2(a,b):c;   }   int a[1010];   int main()   {       int t,n,num,i,j,zero;       scanf("%d",&t);           for(num=1;num<=t;num++)           {               zero=0;               scanf("%d",&n);               j=1;               for(i=1;i<=n;i++)               {                   scanf("%d",&a[j++]);                   if(a[j-1]==0)                   {                       zero=1;                       j--;                   }               }               n=j-1;               for(i=0;i<110;i++)                   for(j=0;j<maxsize;j++)                       dp[i][j]=INT_MIN;               dp[0][size]=0;               for(i=1;i<=n;i++)                   for(j=0;j<maxsize;j++)                       if(j-a[i]>=0&&j+a[i]<maxsize)                           dp[i][j]=max(dp[i-1][j-a[i]]+a[i],dp[i-1][j+a[i]]+a[i],dp[i-1][j]);                       else                       {                           if(j-a[i]<0&&j+a[i]<maxsize)                               dp[i][j]=max2(dp[i-1][j+a[i]]+a[i],dp[i-1][j]);                           else                               if(j+a[i]>=maxsize&&j-a[i]>=0)                                   dp[i][j]=max2(dp[i-1][j-a[i]]+a[i],dp[i-1][j]);                               else                                   dp[i][j]=dp[i-1][j];                       }               if(dp[n][size]==0&&zero==0)                   printf("Case %d: -1\n",num);               else                   printf("Case %d: %d\n",num,dp[n][size]/2);           }          }