P1282 多米诺骨牌

提交 20.02k
通过 6.30k
时间限制 1.00s
内存限制 125.00MB
题目提供者 洛谷
历史分数100

提交记录

查看题解

标签

 
查看算法标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

多米诺骨牌有上下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

思路
　　把所有点数大的置上，对于反转过的卡牌，重量为-1，价值为 2 * (Y - X)，并增加背包原始重量；未反转的，重量为1， 体积为 2 * (X-Y);
　　f[i][j] 表示前 i 张牌的体积为 j 的最小重量。
　　
CODE
 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 template<class T>inline void read(T &res)
10 {
11     char c;T flag=1;
12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
14 }
15 
16 namespace _buff {
17     const size_t BUFF = 1 << 19;
18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
19     char getc() {
20         if (ib == ie) {
21             ib = ibuf;
22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
23         }
24         return ib == ie ? -1 : *ib++;
25     }
26 }
27 
28 int qread() {
29     using namespace _buff;
30     int ret = 0;
31     bool pos = true;
32     char c = getc();
33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
34         assert(~c);
35     }
36     if (c == '-') {
37         pos = false;
38         c = getc();
39     }
40     for (; c >= '0' && c <= '9'; c = getc()) {
41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
42     }
43     return pos ? ret : -ret;
44 }
45 
46 int n;
47 
48 int f[1007][6007];
49 bool vis[1007][6007];
50 
51 int w[1007];
52 int v[1007];
53 
54 int main()
55 {
56     int x, y;
57     scanf("%d",&n);
58     int maxn = 0;
59     int weight = 0;
60     for(int i = 1; i <= n; ++i) {
61         scanf("%d %d",&x, &y);
62         if(x > y) {
63             v[i] = 2 * (x-y);
64             w[i] = 1;
65             maxn += x-y;
66         }
67         if(y > x) {
68             v[i] = 2 * (y-x);
69             w[i] = -1;
70             maxn += y-x;
71             weight++;
72         }
73     }
74     for(int i = 1; i <= n; ++i) {
75         for(int j = 1; j <= maxn; ++j) {
76             f[i][j] = f[i-1][j];
77             vis[i][j] = vis[i-1][j];
78             if(vis[i-1][j-v[i]] || !(j - v[i])) {
79                 if(!vis[i][j]) {
80                     f[i][j] = f[i-1][j-v[i]] + w[i];
81                     vis[i][j] = 1;
82                 }
83                 else {
84                     f[i][j] = min(f[i][j], f[i-1][j-v[i]]+w[i]);
85                 }
86             }
87         }
88     }
89     int q;
90     for(int i = maxn; i >= 1; --i) {
91         if(vis[n][i]) {
92             q = i;
93             break;
94         }
95     }
96     printf("%d\n",weight+f[n][q]);
97     return 0;
98 }
View Code