社区讨论

区间dp，没毛病啊

SSubstitute0329
P4170[CQOI2007] 涂色参与者 3已保存回复 13

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@mi86e8n0
此快照首次捕获于
2025/11/21 09:22
4 个月前
此快照最后确认于
2025/11/21 09:52
4 个月前
查看原帖
CPP
#include<cstdio>
#include<cstring>
using namespace std;
char c[60];
int dp[60][60];
inline int Min(int x,int y){return x<y?x:y;}
int main(){
	memset(dp,127,sizeof dp);
	scanf("%s",c);
	int len=strlen(c);
	for(register int i=0;i<len;i++)
		dp[i][i]=1;
	for(register int i=0;i<len-1;i++)
		for(register int j=i+1;j<len;j++){
			if(c[i]==c[j])dp[i][j]=Min(dp[i+1][j],dp[i][j-1]);
			if(c[i]!=c[j])
				for(register int k=i;k<j;k++)
					dp[i][j]=Min(dp[i][j],dp[i][k]+dp[k+1][j]);
		}
	printf("%d\n",dp[0][len-1]);
	return 0;
}

回复

共 13 条回复，欢迎继续交流。

正在加载回复...