1717 Dominoes

問題概要

上側と下側に数字の書かれたドミノがn枚ある。
上側と下側の数字はそれぞれ0以上6以下である。


ドミノの上側の数字全ての和と、下側の数字全ての和の差を、いくつかのドミノをひっくり返してできるだけ小さくしたい。
そのような最小値を与えるときのドミノをひっくり返す回数の最小値を求めよ。

n≦1000を満たす。

解法

動的計画法による。
ドミノをi枚目まで使って上側の和をjにするのに必要な最小の回数をdp[i][j]とおくと、
次の一枚をひっくり返すかどうかで二通り漸化式が作れてDPできる。


みんな自分の解答よりも速いんだけど、これってオーダー落ちるのだろうか……

ソースコード

int n,u[1000],d[1000],s;
int dp[1001][6001];

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d%d",u+i,d+i),s+=u[i]+d[i];
	rep(i,n+1)rep(j,6*n+1)dp[i][j]=inf;
	
	int mx=0; dp[0][0]=0;
	rep(i,n){
		rep(j,mx+1)if(dp[i][j]!=inf){
			dp[i+1][j+u[i]]=min(dp[i+1][j+u[i]],dp[i][j]);
			dp[i+1][j+d[i]]=min(dp[i+1][j+d[i]],dp[i][j]+1);
		}
		mx+=max(u[i],d[i]);
	}
	
	int ans,d=inf;
	rep(i,mx+1)if(dp[n][i]!=inf){
		int td=abs(s-2*i);
		if(td<d||td==d&&ans>dp[n][i])d=td,ans=dp[n][i];
	}
	printf("%d\n",ans);
	
	return 0;
}