【LuoguP1041】多米诺骨牌
题目链接: https://www.luogu.org/problem/P1282
前言
最近重点做动态规划。今天自己成功推出了两三道题，然后开始水多年未更新的博客？
不能颓废！
分析
首先看数据范围$(N <= 1000, A_i/B_i <= 6)$，那么搜索当然不可能，肯定是考虑动态规划。
还是回归搜索上，比较好分析。一个牌只有两种状态，旋转与不旋转。我们只需要先找到最小差，再考虑最小旋转次数。
再看数据范围，$O(6N^2)$不会超时。我们既要求最小差又要求最小最小旋转次数，又可知所有数的总和是确定的，不如就设个背包。
$F[N(1000)][SUM(6000)]$表示处理到第N个点，上方块的和为SUM时最小的旋转次数。
一开始除$F[0]$为0外都赋值为无穷大，然后转移$A_i$表示上方块,$B_i$表示下方块。
$$F[N][i] = min(F[N - 1][i - A_i], F[N - 1][i - B_i] + 1)$$
然后由于比较闲（怕超空间，然而并不会？）。显然，只要记录N-1的状态，就开了滚动数组$F[2][SUM]$。
最后先找最小差，我们计算$X = \lfloor\frac{SUM}{2} \rfloor$。
如果$SUM$为奇，那么上下差不可能为0，并且上方块和为$X$或$X + 1$时差都为1，因此再设置$Y = X + 1$。
如果$SUM$为偶，那么上方块和为$X$时上下差就为0，$Y = X$。
我们枚举一个数$i$从0开始，不断增大，表示一个范围（大概是这样）。
判断$F[N][X - i]$和$F[N][Y + i]$是否有值，若有则输出小的那个。
代码
代码较丑，推荐自己写代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n, a[1005], b[1005], c[1005], f[2][8000], sum;
int main() {
cin >> n;
for(int i= 1; i <= n; i++) cin >> a[i] >> b[i], c[i]= a[i] - b[i], sum+= a[i] + b[i];
memset(f, 0x3f, sizeof(f));
f[0][0]= 0;
for(int i= 1; i <= n; i++) {
for(int j= 0; j <= sum; j++) f[i & 1][j]= 0x3f3f3f3f;
for(int j= sum; j >= a[i]; j--) f[i & 1][j]= f[(i & 1) ^ 1][j - a[i]];
for(int j= sum; j >= b[i]; j--) f[i & 1][j]= min(f[i & 1][j], f[(i & 1) ^ 1][j - b[i]] + 1);
}
int res= 0x3f3f3f3f, sum1= sum / 2, sum2= sum1 + sum % 2;
for(int i= 0; i < sum; i++) {
if(sum1 + i > n && sum2 - i < 1) break;
res= min(f[n & 1][sum1 + i], f[n & 1][sum2 - i]);
if(f[n & 1][sum1 + i] != 0x3f3f3f3f || f[n & 1][sum2 - i] != 0x3f3f3f3f) break;
}
cout << res << endl;
return 0;
}
|
后记
我的代码必须开8000，如果开8000以下好像会RE。
