#$\color{red}{\mathcal{Description}}$

$Link$

我们有一堆多米诺骨牌，上下两个部分都有点数，$But$我们有一个操作是可以对调上下的点数。若记一块骨牌$i$的上点数为${S_{i,1}}$，下点数为${S_{i,2}}$求在达到$$\sum_{i=1}^{n}{|S_{i,1}-S_{i,12}|}$$最小时的最小操作次数。

#$\color{red}{\mathcal{Solution}}$

这个题在我看到其前面一半时，甚至已经把状态】给想好了：

嗯，这个题接下来的题面一定是这样的：一共最多$m$次操作的机会，可以用或不用，求这个多米诺骨牌序列最大\小的$bulabulabula....$

那么我们不妨令$dp_{i,j,0/1}$表示前$i$个骨牌，一共操作了$j$次，当前不操作/操作的$bulabulabula....$

嗯，生活就是这样充满机遇与挑战

那么记下来我们来看看这道题可以咋做，因为要求的是操作次数，所以我们不应该把操作次数计入状态，那么与操作次数有关系的是差值，看一下数据，差值最大是$5 \times 1000$……好像完全可以接受的样子，那么我们不妨令$dp_{i,j}$表示前$i$个多米诺骨牌，差值为$j$的最小步数。转移就是$$dp_{i,j} = min{dp_{i-1,j+S1-S2}, dp_{i-1,j-S1+S2}+1 }$$或者$$dp_{i,j} = min{dp_{i-1,j+S1-S2}+1, dp_{i-1,j-S1+S2} }$$

哦，滚动数组大法好$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 ;

}

骨牌

[Luogu1282]多米诺骨牌（DP）

#\(\color{red}{\mathcal{Description}}\)

#\(\color{red}{\mathcal{Solution}}\)