题目名称 1205. 多米诺骨牌
输入输出 dom.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2012-10-23
开放分组 全部用户
提交状态
分类标签
动态规划
通过:50, 提交:168, 通过率:29.76%
Gravatar铁桶僵尸 100 0.019 s C++
Gravatarsmart0326 100 0.019 s C++
Gravatar铁桶僵尸 100 0.020 s C++
Gravatar紫葉 100 0.024 s C++
GravatarMoha 100 0.025 s C++
Gravatarnsnsjsjjs 100 0.030 s C++
Gravatarnsnsjsjjs 100 0.030 s C++
Gravatar铁桶僵尸 100 0.031 s C++
GravatarKD35OKC 100 0.032 s C++
GravatarOIdiot 100 0.032 s C++
关于 多米诺骨牌 的讨论
可以转化为背包问题求解
Gravatar王者自由
2012-10-31 10:18 1楼
DPば
GravatarMakazeu
2012-11-01 19:21 2楼
一般的的动归,如果不是怕麻烦开了个暴大的数组和脑残的预处理,效率会高一些
Gravatar天下第一的吃货殿下
2012-11-01 14:37 3楼
曾经,我是一个弱菜。很弱很弱的弱菜。弱到不能行的弱菜,自从我上了paulinsider.at.ua,嘿,腰不酸了,腿不疼了,连思路都痛了。。上http://paulinsider.at.ua/news/2012-11-01-23找题解。。聪明人的选择,你用,我也用。。
GravatarPaulinsider
2012-11-01 20:56 4楼
其实,我原来的程序跑4.0秒,
自从上了http://paulinsider.at.ua/news/2012-11-01-23,程序的腰不酸了,腿不疼了,一口气跑0.4秒!
paulinsider.@at.ua,就是给力!
GravatarTruth.Cirno
2012-11-01 21:46 5楼
吼吼,背包万岁
Gravatardigital-T
2013-08-19 15:31 6楼
凭什么C++没有负下标……
Gravatarcstdio
2014-01-24 16:30 7楼
不开O2用map超时2点。。我不管了
GravatarHouJikan
2014-09-25 22:43 8楼
最后3个点runtimeerror又是w[1001][2]与w[1005][2]的区别。
想起 @Houjikan 大神时常教导我等蒟蒻的一句话:
空间就是用来浪费的。
GravatarEzio
2014-09-24 22:47 9楼
写了半天发现搞错了方程QAQ果然蒟蒻还是蒟蒻
Gravatardevil
2015-07-22 10:07 10楼
不知道为什么,反正使用队列就会超时+爆E。
Gravatarmikumikumi
2015-09-05 23:25 11楼
神奇
GravatarAHOI_521
2016-05-28 21:39 12楼
回复 @Ezio :
同意
GravatarSky_miner
2016-10-10 15:13 13楼
我弱
GravatarRapiz
2016-11-23 17:00 14楼

1205. 多米诺骨牌

★★   输入文件:dom.in   输出文件:dom.out   简单对比
时间限制:1 s   内存限制:128 MB

【问题描述】

多米诺骨牌有上下2个方块组成,每个方块中有1~6个点。现有排成行的n个多米诺骨牌如图8-1所示。


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


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

【输入】

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

【输出】

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

【样例】

dom.in

4

6 1

1 5

1 3

1 2

dom.out

1