蒟蒻使用滚动数组维护上下的和,莫名MLE,求助
查看原帖
蒟蒻使用滚动数组维护上下的和,莫名MLE,求助
555809
houmy楼主2022/12/30 11:08

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];
} 

感谢肯抽出时间帮助我调代码的同学们!

2022/12/30 11:08
加载中...