题解 - 帖子 - Liuser's OJ

P3847 [TJOI2007]调整队形

这个题目可以使用动态规划和记忆化搜索

首先考虑记忆化搜索，待会儿考虑如何将记忆化搜索转化成动态规划

的作用是统计~区间让这个区间变成符合要求的操作的最小值

①当时，不需要进行任何操作，返回0

②当时，如果,那么不需要进行任何操作，返回0。不然的话，至少需要进行一次操作，返回1

③当时，返回，就是说返回它本身和它里面一层区间的最小值

④以上条件都不满足，则则需要取和和还有的最小值，就是说放弃两端，或者放弃左端，或者放弃右端

不多说了，上代码

#include<bits/stdc++.h>
using namespace std;
int n,a[3005],dp[3005][3005];
int dfs(int l,int r){
	if(l==r) return 0;
	if(dp[l][r]!=2139062143) return dp[l][r];
	if(r-l==1){
		if(a[l]==a[r]) return 0;
		else return 1;
	}
	if(a[l]==a[r]) dp[l][r]=min(dp[l][r],dfs(l+1,r-1));
	else dp[l][r]=min(dp[l][r],min(dfs(l+1,r-1)+1,min(dfs(l+1,r)+1,dfs(l,r-1)+1)));
	return dp[l][r];
}
int main(){
	memset(dp,127,sizeof(dp));//记得初始化
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	cout<<dfs(1,n);//最后的答案就是1~n的最小操作次数
	return 0;
}

众所周知，一般情况下，记忆化搜索大部分都是可以转成动态规划的，思路大致差不多，只需要把记忆化搜索的代码改一改，改一改循环的顺序，就可以成功了

在这里，就不细讲了，直接上代码

#include<bits/stdc++.h>
using namespace std;
int n,a[3005],dp[3005][3005];
int main(){
	memset(dp,127,sizeof(dp));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n;i>=1;i--)
		for(int j=i;j<=n;j++){
			if(i==j) dp[i][j]=0;
			if(i+1==j){
				if(a[i]==a[j]) dp[i][j]=0;
				else dp[i][j]=1;
			}
			if(a[i]==a[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
			else dp[i][j]=min(dp[i][j],min(dp[i+1][j-1]+1,min(dp[i+1][j]+1,dp[i][j-1]+1)));
		}
	printf("%d",dp[1][n]);
	return 0;
}

有错还请不吝指正,谢谢！！！

题解

共 4 条回复