九度教程第100题

题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=99

C语言源码：

#include<stdio.h>#include<limits.h>#define maxsize 4010#define size 2000int 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]);elseif(j+a[i]>=maxsize&&j-a[i]>=0)dp[i][j]=max2(dp[i-1][j-a[i]]+a[i],dp[i-1][j]);elsedp[i][j]=dp[i-1][j];}if(dp[n][size]==0&&zero==0)printf("Case %d: -1\n",num);elseprintf("Case %d: %d\n",num,dp[n][size]/2);}}