ZJUT1476 礼物放置

#include <cstdio>
int maxone(int a, int b){return a<b?b:a;}

int f[11000];
int back[11000];

int main()
{
	int n;
	while (scanf("%d",&n)!=EOF)
	{
		int i,j;
		int gift[110],cou=0;
		int mid = 0;
		for (i=0;i<n;i++)
		{
			scanf("%d",gift+i);
			mid += gift[i];
		}
		for (i=0;i<=mid;i++)
		{
			f[i] = -1;
			back[i] = -1;  //没重置错误了很多次
		}
		f[0] = 0;
		for (j=0;j<n;j++)
		{
			int _cou = cou;
			for (i=0;i<=cou;i++)
			{
				back[i]=f[i];
			}
			for (i=0;i<=cou;i++)
			{
				if (f[i] >= 0)
				{
					if (i + gift[j] <= mid)
					{
						back[i+gift[j]] = maxone(f[i]+gift[j],back[i+gift[j]]);
						_cou = maxone(i+gift[j], cou);
					}
					if (i >= gift[j])
					{
						back[i-gift[j]] = maxone(back[i-gift[j]], f[i]);
					}
				}
			}
			for (i=0;i<=_cou;i++)
			{
				f[i]=back[i];
			}
			cou = _cou;
		}
		if (f[0] == 0) printf("-1\n"); else printf("%d\n",f[0]);
	}
	return 0;
}