题目描述
多米诺骨牌有上下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; }
没有帐号? 立即注册