题解 P1282 【多米诺骨牌】

看到没有滚动数组的题解……哼，为什么没有卡空间呢qwq！？

首先我们看这个题，是个dp，线性单项递推第一维好像并没有什么问题。那我们不妨设dp[i][j]表示前i个物品，上下差值总和为j的最小交换次数。那么有一个显然的init是

#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][ 不确定 ]，所以我们可以滚去一维。那么最终的核心代码就长这个样：

    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次）

    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

#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行（亲测）