记录编号	185308	评测结果	AAAAAAAAAA
题目名称	多米诺骨牌	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.383 s
提交时间	2015-09-05 23:24:02	内存使用	46.94 MiB

#include<cstdio>
#include<deque>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
using namespace std;
const int INF=0x7fffffff/2,detla=6000;
int N,d[1010]={0};
int f[1010][12100]={0};
deque<int> Q;
void work()
{
	Q.push_back(0);
	f[0][detla]=0;
	for(int i=1;i<=N;i++)
	{
		int M=Q.size();
		for(int x=-6*i;x<=6*i;x++)
		{
			if(f[i-1][x+detla]==INF) continue;
			f[i][x+detla+d[i]]=min(f[i][x+detla+d[i]],f[i-1][x+detla]+1);
			f[i][x+detla-d[i]]=min(f[i][x+detla-d[i]],f[i-1][x+detla]);
			//cout<<i<<" "<<x<<" "<<x+d[i]<<" "<<f[i][x+detla+d[i]]<<endl;
			//cout<<i<<" "<<x<<" "<<x-d[i]<<" "<<f[i][x+detla-d[i]]<<endl;
		}
	}
	int now=INF,ans=0;
	for(int j=-6*N;j<=6*N;j++)
	{
		if(f[N][j+detla]!=INF&&abs(j)<now)
		{
			now=abs(j);
			ans=f[N][j+detla];
		}
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("dom.in","r",stdin);
	freopen("dom.out","w",stdout);
	scanf("%d",&N);
	int a,b;
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&a,&b);
		d[i]=a-b;
	}
	for(int i=0;i<=N;i++) for(int j=-6*N;j<=6*N;j++) f[i][j+detla]=INF;
	work();
	return 0;
}