记录编号	47535	评测结果	AAAAAAAAAA
题目名称	多米诺骨牌	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.417 s
提交时间	2012-11-01 21:41:18	内存使用	61.00 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int a[1010],b[1010],c[1010],get[1010][12010];
bool f[1010][12010];

int absint(int a)
{
	if (a<0)
		return(-a);
	return(a);
}

int minint(int a,int b)
{
	if (a<b)
		return(a);
	return(b);
}

int main(void)
{
	freopen("dom.in","r",stdin);
	freopen("dom.out","w",stdout);
	int i,j,n,suma=0,sumb=0,mindis,minget;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		c[i]=(b[i]-a[i])<<1;
		suma+=a[i];
		sumb+=b[i];
	}
	mindis=suma-sumb;
	minget=0;
	f[0][mindis+6000]=true;
	for (i=1;i<=n;i++)
	{
		for (j=-6000;j<=6000;j++)
		{
			if (f[i-1][j+6000])
			{
				f[i][j+6000]=true;
				get[i][j+6000]=get[i-1][j+6000];
			}
			if (j-c[i]>=-6000&&j-c[i]<=6000)
				if (f[i-1][j+6000-c[i]])
				{
					f[i][j+6000]=true;
					if (!f[i-1][j+6000])
						get[i][j+6000]=get[i-1][j+6000-c[i]]+1;
					else
						get[i][j+6000]=minint(get[i][j+6000],get[i-1][j+6000-c[i]]+1);
					if (absint(mindis)>absint(j))
					{
						mindis=j;
						minget=get[i][j+6000];
					}
					else if (absint(mindis)==absint(j))
					{
						minget=minint(minget,get[i][j+6000]);
					}
				}
		}
	}
	cout<<minget<<endl;
	return(0);
}