• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【LG P4170】涂色

admin

11月 28, 2021

解析

题意是求对字符串的最少染色次数,设 f[i][j] 为字符串的子串 s[i] ~ s[j] 的最少染色次数,我们分析一下:

i==j 时,子串明显只需要涂色一次,于是 f[i][j]=1

i!=js[i]==s[j] 时,可以想到只需要在首次涂色时多涂一格即可,于是 f[i][j]=min(f[i][j-1],f[i+1][j])

i!=js[i]!=s[j] 时,我们需要考虑将子串断成两部分来涂色,于是需要枚举子串的断点,设断点为 k,那么 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])

总结一下就是:

[egin{equation}
f_{i,j}=
egin{cases}
1 & i=j\
min(f_{i,j-1},f_{i+1,j}) & i
ot=j,s_i=s_j\
min(f_{i,j},f_{i,k}+f_{k+1,j}) & i
ot=j,s_i
ot=s_j
end{cases}
end{equation}
]

由于 f[i][j] 的定义,我们可以知道 f[1][n] 即为答案。

代码

#include<bits/stdc++.h>
using namespace std;
char c[55];
int f[55][55];
int main() {
	scanf("%s",c+1);
	int n=strlen(c+1);
	memset(f,0x7F,sizeof(f));
	for(int i=1; i<=n; i++) {
		f[i][i]=1;
	}
	for(int i=2; i<=n; i++) {
		for(int l=1; l<=n; l++) {
			int r=l+i-1;
			if(r>n) {
				break;
			}
			if(c[l]==c[r]) {
				f[l][r]=min(f[l+1][r],f[l][r-1]);
			} else {
				for(int k=l; k<r; k++) {
					f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
				}
			}
		}
	}
	printf("%d",f[1][n]);
	return 0;
}

参考资料

P4170 涂色 – Loner_Knowledge 的博客 – 洛谷博客

知识共享许可协议

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

限于本人水平,如果文章有表述不当之处,还请不吝赐教。

发表评论

您的电子邮箱地址不会被公开。