P1282 多米诺骨牌

题目描述

多米诺骨牌有上下2个方块组成，每个方块中有1~6个点。现有排成行的

上方块中点数之和记为S1，下方块中点数之和记为S2，它们的差为|S1-S2|。例如在图8-1中，S1=6+1+1+1=9，S2=1+5+3+2=11，|S1-S2|=2。每个多米诺骨牌可以旋转180°，使得上下两个方块互换位置。编程用最少的旋转次数使多米诺骨牌上下2行点数之差达到最小。

Solution

先明确题意：

每个物品有两个状态：正着的和倒着的

求最小差值意义下的最小旋转次数

首先看这个差值最小，发现下值 = 总值 - 上值，于是我们统计一侧和即可计算差值

然后设计一下状态，题目求最小旋转次数，那么dp数组表示的应该是最小次数，又有最小差值限制显然要引入一维一侧和作为状态

设计dp状态的关键是看 如下状态是否只对应一个最值

于是 \(dp[i][j]\) 表示考虑前 \(i\) 个，上侧和为 \(j\) 的最小旋转次数

边界为第一个不转 ---> \(dp[1][up[1]] = 0\)

转 ---> \(dp[1][down[1]] = 1\)

注意当 \(up[1] == down[1]\) 时不用旋转，两个值都为 0

转移直接看转不转即可，类似 01背包

注意 \(j\) 的状态最大有 \(6n\)

然后考虑优化的话可以让最大状态为 \(\sum_{i = 1}^{n}max(up_{i}, down_{i})\)

还可以滚动数组

懒就不写了

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 2019, inf = 1e9;

int num;

int a[maxn], b[maxn], sum;

int dp[maxn][maxn * 6];//表示前i个骨牌，上面和为j的最小交换数

void init(){

	num = RD();

	REP(i, 1, num)a[i] = RD(), b[i] = RD(), sum += a[i] + b[i];

	REP(i, 1, num)REP(j, 1, num * 6)dp[i][j] = inf;

	if(a[1] == b[1])dp[1][a[1]] = dp[1][b[1]] = 0;

	else dp[1][a[1]] = 0, dp[1][b[1]] = 1;

	}

void solve(){

	REP(i, 1, num){

		REP(j, 1, num * 6){//最多状态数

			if(dp[i][j] == inf)continue;//防越界就打了个刷表法

			dp[i + 1][j + a[i + 1]] = min(dp[i + 1][j + a[i + 1]], dp[i][j]);//不转

			dp[i + 1][j + b[i + 1]] = min(dp[i + 1][j + b[i + 1]], dp[i][j] + 1);//转

			}

		}

	int minS = inf, ans;

	REP(i, 1, num * 6){

		if(dp[num][i] == inf)continue;

		int now = abs((sum - i) - i);

		if(now < minS){

			minS = now;

			ans = dp[num][i];

			}

		else if(now == minS)ans = min(ans, dp[num][i]);

		}

	printf("%d\n", ans);

	}

int main(){

	init();

	solve();

	return 0;

	}

巴特西

P1282 多米诺骨牌

P1282 多米诺骨牌

Solution

Code

最新文章

热门文章