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