【POJ1717】Dominoes (动态规划,背包变形)

Categories: 数据结构和算法
Tags: ,
Comments: 1 Comment
Published on: 2011 年 05 月 09 日

A domino is a flat, thumbsized tile, the face of which is divided into two squares, each left blank or bearing from one to six dots. There is a row of dominoes laid out on a table:
The number of dots in the top line is 6+1+1+1=9 and the number of dots in the bottom line is 1+5+3+2=11. The gap between the top line and the bottom line is 2. The gap is the absolute value of difference between two sums.
Each domino can be turned by 180 degrees keeping its face always upwards.
What is the smallest number of turns needed to minimise the gap between the top line and the bottom line?
For the figure above it is sufficient to turn the last domino in the row in order to decrease the gap to 0. In this case the answer is 1.
Write a program that: computes the smallest number of turns needed to minimise the gap between the top line and the bottom line.
题意:题目给出两列数,为了使两列数的和之间的差距(gap)变小,
可以交换对应位置的数字,求出当gap最小的时候,最少的交换
次数。
f[i] 表示两列数中的一列和为 i的时候,所需的最小交换次数,
初始化为 ∞,f[0] = 0;每增加一组数,从以前的状态推出当
前转台,注意要把以前状态删掉。
if f[i] != INF
f[i+x] = min ( f[i+x] , f[i] ),
f[i+y] = min ( f[i+y], f[i] + 1),
最后,从总和的一半开始往前,往后各找到一个状态,
找出这两个状态的最优的就是所求。

#include <cstdio>
#include <cstring>
const int M = 12005, INF = 10000000;
int f[M], n;
int main(){
	int i, j, x, y, sum, tmp;
	while (scanf ("%d", &n) != EOF){
		for (i = 1; i < M; i++)
			f[i] = INF;
		f[0] = 0,sum = 0;
		for (i = 0; i < n; i++){
			scanf ("%d %d", &x, &y);
			sum += (x + y);
			for (j = sum; j >= 0; j--)
				if (f[j] < INF){
					tmp = f[j];
					f[j] = INF; 
					if (f[j+x] > tmp)
						f[j+x] = tmp;
					if (f[j+y] > tmp + 1)
						f[j+y] = tmp + 1;
				}
		}
		for (i = sum / 2; i >= 0; i--)
			if (f[i] < INF) break;
		for (j = (int)((double)sum/2.0+0.5); j < M; j++)
			if (f[j] < INF) break;
		printf ("%d\n", f[i] < f[j] ? f[i] : f[j]);
	}
}

我猜你可能也喜欢:

1 Comment - Leave a comment
  1. 郑晓鹏说道:

    看过代码和分析不太明白为什么要每次需要重置以前的状态

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日