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

這題就難了,我真的想不到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;
}

出處:http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=d091
參考:https://www.itread01.com/content/1545447844.html

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *