记录编号	68305	评测结果	AAAAAAAAAA
题目名称	多米诺骨牌	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2013-08-19 15:30:30	内存使用	0.40 MiB

#include<fstream>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
ifstream fi("dom.in");
ofstream fo("dom.out");
const int INF=5001;
struct dom
{
	int a,b;
}d[1001];
int n,bag[20001];
int main()
{
	fi>>n;
	int i,j,st=10000;
	for(i=1;i<=n;i++)
	{
		fi>>d[i].a>>d[i].b;
		st+=(d[i].a-d[i].b);
	}
	for(i=10000-5*n;i<=10000+5*n;i++)
		bag[i]=INF;
	bag[st]=0;
	int tmp;
	for(i=1;i<=n;i++)
	{
		tmp=(d[i].b-d[i].a)*2;
		if(tmp==0)continue;
		if(tmp>0)
		{
			for(j=10000+5*n-tmp;j>=10000-5*n;j--)
				if(bag[j]!=INF)
				{
					bag[j+tmp]=min(bag[j]+1,bag[j+tmp]);
				}
		}
		if(tmp<0)
		{
			for(j=10000-5*n+tmp;j<=10000+5*n;j++)
			if(bag[j]!=INF)
			{
				bag[j+tmp]=min(bag[j]+1,bag[j+tmp]);
			}
		}
	}
	st=0;
	while(bag[10000+st]==INF&&bag[10000-st]==INF)
		st++;
	fo<<min(bag[10000+st],bag[10000-st]);
	return 0;
}