洛谷P1282 多米诺骨牌
? 解题记录 ? ? 洛谷 ? ? 动态规划 ?    2017-09-28 21:20:19    654    0    0

题目描述

多米诺骨牌有上下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行点数之差达到最小。

对于图中的例子,只要将最后一个多米诺骨牌旋转180°,可使上下2行点数之差为0。

输入输出格式

输入格式:

 

输入文件的第一行是一个正整数n(1≤n≤1000),表示多米诺骨牌数。接下来的n行表示n个多米诺骨牌的点数。每行有两个用空格隔开的正整数,表示多米诺骨牌上下方块中的点数a和b,且1≤a,b≤6。

 

输出格式:

 

输出文件仅一行,包含一个整数。表示求得的最小旋转次数。

 

输入输出样例

输入样例#1:
4
6 1
1 5
1 3
1 2
输出样例#1:
1

最开始乱yy了一个看似很可行的方法,想到把所有的骨牌处理成上减下, 然后把正数负数都做同一个空间大小的完全背包,二分这个空间大小,最后选择的正负数个数的和就是答案。

但是看这道题的数据范围,且不说代码的可行性,就是复杂度就已经GG了。看来我们要另辟蹊径——向题解低头

首先可以用dp[i][j][k]表示第i个时上面和j,下面和为k。不过大家肯定觉得我说的是废话。看看本题的数据,不说时间问题,空间已经报表。其实由P1373的思想,我们发现j、k两维状态是冗杂的,可以合并为一维。为什么呢?因为答案需要统计的只是差值,我们并不需要确切的j、k值。于是,我们用dp[i][t]表示第i个位置的上端 - 下端的值为t。就轻松的解决了时空问题。

状态转移方程:dp[i][j] = min(dp[i - 1][j - num[i][1] + num[i][0]] + 1, dp[i - 1][j - num[i][0] + num[i][1]]);

本题还有一点需要注意,因为差值可以是负数,我们需要平移数组才能不让下标越界。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define move(a) ((a) + 5005)
using namespace std;
const int maxn = 1e3 + 5;
int dp[maxn][maxn * 10], n, id;
int num[maxn][2];

int main() {
	scanf("%d", &n);
	for(register int i = 1; i <= n; ++i) 
		scanf("%d%d", &num[i][0], &num[i][1]);
	memset(dp, 0x3f, sizeof(dp));
	dp[1][move(num[1][1] - num[1][0])] = 1;
	dp[1][move(num[1][0] - num[1][1])] = 0;
	for(register int i = 2; i <= n; ++i) 
		for(register int j = -n * 5; j <= n * 5; ++j) 
			dp[i][move(j)] = min(dp[i - 1][move(j - num[i][1] + num[i][0])] + 1, dp[i - 1][move(j - num[i][0] + num[i][1])]);
	for(register int i = 0; i <= n * 5; ++i) {
		if(dp[n][move(i)] != 0x3f3f3f3f) {
			printf("%d", dp[n][move(i)]);
			return 0;
		}
		if(dp[n][move(-i)] != 0x3f3f3f3f) {
			printf("%d", dp[n][move(-i)]);
			return 0;
		}
	}
	return 0;
}


上一篇: 洛谷P1169 [ZJOI2007]棋盘制作

下一篇: 洛谷P1220 关路灯

654 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航