当前位置: 代码迷 >> 综合 >> 洛谷 P1282 多米诺骨牌
  详细解决方案

洛谷 P1282 多米诺骨牌

热度:98   发布时间:2023-09-20 19:14:17.0

这道题很有收获。

我自己想的时候有想到这是一个背包,但是写的实现非常麻烦,还是错的。

我想的是在背包的过程中尽量靠近0,但是这样显然有后效性
而且我思考背包的方式不对。要考虑当前物品有哪几种可能,然后
比如这道题就是交换或者不交换。先用二维的思考方式,滚动数组
只是后面的优化。

后来看了题解,很有收获

 

(1)如何防止下标为负数。可以设一个基准数base,然后每次涉及到重量的
都加上base,这个base的值是负数的最小值。同时注意数组空间就要开大一些。
这样就避免了负数下标
(2)先做后统计答案。f[i][j]是前i个骨牌构成和为j的最小交换次数。
这个答案涉及到最小的数以及次数,一个作维度,一个作值,这样最后
扫遍数组就可以得出答案。并不是说最后一定要输出f[n][m]什么的。
这样的思路非常棒。

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;const int MAXN = 1123;
const int base = 5000;
int a[MAXN], b[MAXN], f[MAXN][base*2+10], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i], &b[i]);memset(f, 0x3f, sizeof(f));f[0][0+base] = 0;_for(i, 1, n)_for(j, -base, base){int t = a[i] - b[i];f[i][j+base] = min(f[i-1][j-t+base], f[i-1][j+t+base] + 1); }_for(j, 0, base){int t = min(f[n][j+base], f[n][-j+base]);if(t <= 1000){printf("%d\n", t);break;}}	return 0;
}

滚动数组优化版本(时间甚至还少了。看来空间减少时间也会减少一些。)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++) 
#define _for(i, a, b) for(int i = (a); i <= (b); i++) 
using namespace std;const int MAXN = 1123;
const int base = 5000;
int a[MAXN], b[MAXN], f[2][base*2+10], n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &a[i], &b[i]);memset(f, 0x3f, sizeof(f));int p = 1;f[p][0+base] = 0;_for(i, 1, n){p ^= 1;_for(j, -base, base){int t = a[i] - b[i];f[p][j+base] = min(f[p^1][j-t+base], f[p^1][j+t+base] + 1); }}_for(j, 0, base){int t = min(f[p][j+base], f[p][-j+base]);if(t <= 1000){printf("%d\n", t);break;}}	return 0;
}