rt,状态定义写在注释里了。
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
/*
dp[i][j][k] - 前i个骨牌中,第一行总和为j,第二行总和为k的最少旋转次数
dp[i][j][k]=min(dp[i-1][j-b[i]][k-a[i]]+1,dp[i-1][j-a[i]][k-b[i]])
第一维使用滚动数组
*/
int n,a[1010],b[1010];
int dp[2][6010][6010];//最大n=1000,1000*6=6000
int ans[6010];//在差为i时最少旋转次数
int main(){
memset(ans,0x7f,sizeof(ans));
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
memset(dp,0x7f,sizeof(dp));
dp[0][0][0]=true;
for(int i=1;i<=n;i++){
for(int j=0;j<=6*i;j++){
for(int k=0;k<=6*i;k++){
dp[1][j][k]=0x7f7f7f7f;
if(j>=b[i]&&k>=a[i])dp[1][j][k]=min(dp[1][j][k],dp[0][j-b[i]][k-a[i]]+1);
if(j>=a[i]&&k>=b[i])dp[1][j][k]=min(dp[1][j][k],dp[0][j-a[i]][k-b[i]]);
// cout<<"前"<<i<<"个骨牌中,第一行总和为"<<j<<",第二行总和为"<<k<<"的最少旋转次数是"<<dp[1][j][k]<<endl;
}
}
memcpy(dp[0],dp[1],sizeof(dp[1]));
}
for(int j=0;j<=6*n;j++){
for(int k=0;k<=6*n;k++){
if(dp[0][j][k]==0x7f7f7f7f)continue;
int d=abs(j-k);
ans[d]=min(ans[d],dp[0][j][k]);
}
}
int minD=0;
for(int i=0;i<=6*n;i++){
if(ans[i]!=0x7f7f7f7f){
minD=i;
break;
}
}
cout<<ans[minD];
}
感谢肯抽出时间帮助我调代码的同学们!