1717:Dominoes

keyword

動的計画法　C++

概要

n(<1000)組の(x,y)(0<=x,y<=6)が与えられる。いくつかのx,yをスワップしてsum(x)とsum(y)の差を最小にしたい。その値を達成するのに必要な最小のスワップ回数を求める問題。
dp[n][(xの部分和)-(yの部分和)]で解く。計算量は6*2*n^2位。多分適当に順番入れ替えたりすればもうちょっと計算量を落とせるはず。この解き方だとメモリ制限が厳しい。

int main(){
    int i, j, n, x;
    static int dp[1002][12002];

    n = readint();

    REP(i,n){
        REP(j,12001){
            dp[i][j] = 1<<30;
        }
    }

    x = readint() - readint();
    dp[0][6000-x] = 1;
    dp[0][6000+x] = 0;

    REP(i,n-1){
        x = readint() - readint();
        REP(j,12001)if(dp[i][j] < 1<<30){
            dp[i+1][j+x] = min(dp[i+1][j+x], dp[i][j]);
            dp[i+1][j-x] = min(dp[i+1][j-x], dp[i][j] + 1);
        }
    }

    x = 1<<30;
    REP(i,6001){
        x = min(dp[n-1][6000-i], dp[n-1][6000+i]);
        if(x < 1<<30) break;
    }

    printf("%d\n", x);
    return 0;
}