rnqoj-72-拔河比赛

#include<stdio.h>  
#include<string.h>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
#define INF 99999999  
int dp[10001][101];  
int t[10001][101];  
int main()  
{  
    int n,i,j,k;  
    int a[101];  
    int s=0;  
    scanf("%d",&n);  
    for(i=1;i<=n;i++)scanf("%d",&a[i]),s+=a[i];;  
    memset(dp,-1,sizeof(dp));  
    dp[0][0]=0;  
    for(i=1;i<=n;i++)  
    {  
        for(j=s;j>=a[i];j--)  
        {  
            for(k=n;k>=1;k--)  
            {  
                if(j-a[i]>0&&k==1)continue;  
                if(dp[j-a[i]][k-1]!=-1)  
                {  
                    dp[j][k]=dp[j-a[i]][k-1]+1;  
                    t[j][k]=1;  
                }  
            }  
        }  
    }  
    for(i=s/2;i<=s;i++)  
    {  
        for(j=0;j<=n;j++)  
            if(dp[i][j]!=-1)  
            {  
                cout<<((2*i-s)>0?(2*i-s):(s-2*i))<<endl;  
                break;  
            }  
        if(j!=n+1)break;  
    }  
    return 0;  
}