[Poj #1717] Dominoes

dp[i][j]表示前i张多米诺骨牌得到差值总和j的最小翻转次数。
dp完找最接近0的j即可。
注意处理负值。

#include<cstdio>
#include<cstring>
using namespace std;
int maxf(int x,int y){return x>y?x:y;}
int minf(int x,int y){return x<y?x:y;}
const int base=5000;
const int inf=0x7f7f7f7f;
int a[10010],b[10010];
int dp[1010][10010];
int main()
{
	int n,m,i,j,k,x,y,z,ans,pos;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	scanf("%d%d",&a[i],&b[i]);
	memset(dp,0x7f,sizeof(dp));
	if(a[1]!=b[1])
        dp[1][a[1]-b[1]+base]=0,dp[1][b[1]-a[1]+base]=1;
	else 
        dp[1][a[1]-b[1]+base]=dp[1][b[1]-a[1]+base]=0;
	for(i=2;i<=n;i++)
	{
		for(j=-base;j<=base;j++)
		{
			dp[i][j+base]=minf(dp[i][j+base],dp[i-1][j+b[i]-a[i]+base]);
			dp[i][j+base]=minf(dp[i][j+base],dp[i-1][j+a[i]-b[i]+base]+1);
		}
	}
	for(i=0;i<=base;i++)
	{
		if(dp[n][i+base]!=inf)
		{
			pos=i;
			ans=dp[n][i+base];
			break;
		}
	}
	for(i=0;i>=-base;i--)
	{
		if(dp[n][i+base]!=inf)
		{
			if(-i<pos)
			{
				pos=-i;
				ans=dp[n][i+base];
				break;
			}
			else if(-i==pos)
			{
				ans=minf(ans,dp[n][i+base]);
			}
		}
	}
	printf("%d
",ans);
	return 0;
}
/*
//sample
4
6 1
1 5
1 3
1 2
ans:1
*/