多米诺骨牌

链接

首先先定义dp[i][j] (表示前i个合并后值为j的最小翻转次数)

我们先计算每一组的差值d[i]

显然,对于每一个已经存在的dp[i][j],对于下一个i也就是dp[i+1],有两种可能

不翻转:dp[i+1][j+d[i]]=dp[i][j]

翻转:dp[i+1][j-d[i]]=dp[i][j]+1

这样相当于遍历所有可能,理论上时间复杂度会非常大,但是由于范围的限制和重叠,时间复杂度也就限制在了O(n²),可以接受

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const int INF=0x3f3f3f3f;
int d[MAXN];
int dp[MAXN][20005];


int main(){
    memset(dp,0x3f,sizeof(dp));
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        d[i]=a-b;
    }
    dp[0][5*n]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=10*n;j++){
            if(dp[i-1][j]!=INF){
            if(j+d[i]<=10*n)dp[i][j+d[i]]=min(dp[i-1][j],dp[i][j+d[i]]);
            if(j-d[i]>=0)dp[i][j-d[i]]=min(dp[i][j-d[i]],dp[i-1][j]+1);
            }
        }
    }
    for(int i=0;i<=5*n;i++){
        if(dp[n][5*n-i]==INF&&dp[n][5*n+i]==INF) continue;
        int ans=min(dp[n][5*n-i],dp[n][5*n+i]);
        cout<<ans<<'\n';
        return 0;
    }
    
}

时间复杂度:O(n²)

空间复杂度:O(n²)