C++ 台中區 106-7 雙層骨牌

參考資料：動態規劃】 多米諾骨牌 （ssl 1632/luogu 1282） – IT閱讀

O(q2)以內的解，有點像01背包。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define INF 32000

int q,d;
short dp[1005][12010];

int main(){
    cin>>q;
    int up,dw;
    for(int i=0;i<1050;i++){
        for(int j=0;j<12010;j++) dp[i][j]=INF;
    }

    const int mx=6*q;
    dp[0][mx]=0;
    for(int i=1;i<=q;i++){
        cin>>up>>dw;
        d=up-dw;
        for(int j=mx-i*6;j<=mx+i*6;j++){
            dp[i][j]=min(dp[i-1][j-d],dp[i-1][j+d]+1);
        }
    }

    int k=mx;
    while(dp[q][k]==INF) k++;
    cout<<dp[q][k]<<"\n"<<k-mx;
    return 0;
}