题解 P1282 【多米诺骨牌】
皎月半洒花
2018-07-20 18:58:29
看到没有滚动数组的题解……哼，为什么没有卡空间呢qwq！？
首先我们看这个题，是个$dp$，线性单项递推第一维好像并没有什么问题。那我们不妨设$dp[i][j]$表示前$i$个物品，上下差值总和为$j$的最小交换次数。那么有一个显然的$init$是
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std ;
const int MAXN = 1010, NN = 5050 ; int out ;
int i, j, k, N, A[MAXN], B[MAXN], dp[MAXN][NN << 1] ;
int main(){
cin >> N ;
memset(dp, 0x7f, sizeof(dp)) ;
dp[0][NN] = 0 ;
...........
}
```
然后我们思考状态转移方程$$dp_{i, j} = min\{dp_{i, j - a_i+b_i}, dp_{i,j+a_i-b_i}+1 \}$$
类似于一个背包吧，那其实就是由翻或不翻转移过来的而已。诶，还有一点，由于是差值嘛，那么$A[i]-B[i]$在前者还是在后者，都是一样的，所以另一个方程当然也可以啊。$$dp_{i, j} = min\{dp_{i, j + a_i-b_i}, dp_{i,j-a_i+b_i}+1 \}$$
但是我们考虑，其实第一维是没有必要的，因为我们最终的状态是确定的即$dp[n][$ 不确定 $]$，所以我们可以滚去一维。那么最终的核心代码就长这个样：
```cpp
cin >> N ; memset(dp, 0x7f, sizeof(dp)) ; dp[0][NN] = 0 ;
for(i = 1; i <= N; i ++) scanf("%d%d", &A[i], &B[i]) ;
for(k = i = 1; i <= N; i ++, k ^= 1){
memset(dp[k], 0x7f, sizeof(dp[k])) ;
for(j = -5000; j <= 5000; j ++)
dp[k][j + NN] = min(dp[k ^ 1][j + A[i] - B[i] + NN], dp[k ^ 1][j - A[i] + B[i] + NN] + 1) ; ;
}
```
咳咳，不知为什么迷恋上了压行$emmm$。
那么，由于我们的第二维$j$是单调的，所以我们从前往后扫一遍，遇到合法的就输出即可（合法：$\leq1000$，因为题目中至多交换$1000$次）
```cpp
for(i = 0; i <= 5000; i ++){
out = min(dp[N & 1][i + NN], dp[N & 1][-i + NN]) ;
if(out <= 1000) { cout << out ; break ;}
}
```
嗯，最后贴一波标称吧$qwq$
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std ;
const int MAXN = 1010, NN = 5050 ; int out ;
int i, j, k, N, A[MAXN], B[MAXN], dp[2][NN << 2] ;
int main(){
cin >> N ; memset(dp, 0x7f, sizeof(dp)) ; dp[0][NN] = 0 ;
for(i = 1; i <= N; i ++) scanf("%d%d", &A[i], &B[i]) ;
for(k = i = 1; i <= N; i ++, k ^= 1){
memset(dp[k], 0x7f, sizeof(dp[k])) ;
for(j = -5000; j <= 5000; j ++)
dp[k][j + NN] = min(dp[k ^ 1][j + A[i] - B[i] + NN], dp[k ^ 1][j - A[i] + B[i] + NN] + 1) ; ;
}
for(i = 0; i <= 5000; i ++){
out = min(dp[N & 1][i + NN], dp[N & 1][-i + NN]) ;
if(out <= 1000) { cout << out ; break ;}
} return 0 ;
}
```
~~你甚至可以把它压到15行（亲测）~~