记录编号	86306	评测结果	AAAAAAAAAA
题目名称	多米诺骨牌	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.129 s
提交时间	2014-01-24 16:30:10	内存使用	46.18 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
using namespace std;
const int SIZEN=1001,DELTA=6000,INF=0x7fffffff;
int N;
int d[SIZEN]={0};
int f[SIZEN][2*6*SIZEN]={0};
int main(){
	freopen("dom.in","r",stdin);
	freopen("dom.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		d[i]=a-b;
	}
	for(int i=0;i<=N;i++) for(int j=-6*i;j<=6*i;j++) f[i][j+DELTA]=INF;
	f[0][0+DELTA]=0;
	for(int i=0;i<N;i++){
		for(int j=-6*i;j<=6*i;j++){
			if(f[i][j+DELTA]!=INF){
				f[i+1][j+d[i+1]+DELTA]=min(f[i+1][j+d[i+1]+DELTA],f[i][j+DELTA]+1);
				f[i+1][j-d[i+1]+DELTA]=min(f[i+1][j-d[i+1]+DELTA],f[i][j+DELTA]);
			}
		}
	}
	int ans=INF,ansst;
	for(int i=-6*N;i<=6*N;i++){
		if(f[N][i+DELTA]!=INF&&abs(i)<ans){
			ans=abs(i);
			ansst=f[N][i+DELTA];
		}
	}
	printf("%d\n",ansst);
	return 0;
}