P1282 多米诺骨牌

标签：maxx 多米诺骨牌 骨牌 int P1282 点数 dp define

题意：有一堆多米诺骨牌，骨牌被分为上下两部分，每部分写有1-6的一个数（真的不是骰子吗）。试颠倒一部分骨牌，使得所有骨牌  上部点数之和  和  下部点数之和  之差  最小。求颠倒骨牌的最小个数。

解：点数很小，每部分和最大是6000，想设dp[i][j]为上面点数为i，下面点数为j的最小次数。转移复杂度O(n)，整体6000*6000*1000，需要压一压。显然点数之和是固定的，只要记录上边点数之和就行了。dp[i][j]为到第i个骨牌为止上部之和为j的最小次数，把到第几个骨牌写进状态，少动点脑子。最后遍历一遍找答案。

代码：

#include <bits/stdc++.h>
using namespace std;
#define maxx 1005
#define maxn 25
#define maxm 205
#define ll long long
#define inf 1000000009
#define mod 998244353
int a[maxx],b[maxx];
int dp[maxx][6005]={0};
signed main() {
//    int T;
//    scanf("%d",&T);
//    while(T--){
//
//    }
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    int sum=0;
    for(int i=1;i<=n;i++){
        sum+=(a[i]+b[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=6000;j++){
            dp[i][j]=7000;
        }
    }
    dp[1][a[1]]=0;dp[1][b[1]]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=6000;j++){
            if(j-a[i]>0) dp[i][j]=min(dp[i][j],dp[i-1][j-a[i]]);
            if(j-b[i]>0) dp[i][j]=min(dp[i][j],dp[i-1][j-b[i]]+1);
        }
    }
    int ans=7000,res=7000;
    for(int i=1;i<=6000;i++){
        if(dp[n][i]<=1000){
            if(abs(i+i-sum)<res){
                res=abs(i+i-sum);
                ans=dp[n][i];
            }
            if(abs(i+i-sum)==res) ans=min(ans,dp[n][i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}
//dp[i][j] the i th, the sum of upper is j, min rotate times

View Code

 

 

标签：maxx,多米诺骨牌,骨牌,int,P1282,点数,dp,define
From： https://www.cnblogs.com/capterlliar/p/16825753.html