ural 1005 Stone Pile

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;
int dp[1000005];  //数组必须开到100W以上
int main()
{
    int n,i,j;
    int a[25];
    scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    int ans=0;
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        ans+=a[i];
    }
    int sum=ans/2;
    for(i=0; i<n; i++)
    {
        for(j=sum; j>=a[i]; j--)
        {
            dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
        }
    }
    printf("%d\n",ans-dp[sum]*2);
    return 0;
}