字符串涂漆
时间:2022-05-11 07:03
昨晚想了一晚上,最后还是看题解了/kk
约用时 20min。
因为要考虑到原来的字符串有的字母是可以保留的,所以在按的方法求过一遍之后,还需要再次决策。
设 g[i] 表示从 1 ~ i 所需的最少次数,则分为两种情况:
-
当
a[i] == b[i]
时,也就是说第 i 个位置就不用涂了,保留原来的颜色即可,所以g[i]=g[i-1]
。 -
否则枚举分界点,而对于分界点 j ,它的代价就是 1 ~ j(不含 j ) 的最小次数加上 j ~ i(含 i,j ) 的最小次数,也就是
g[i]=g[j-1]+f[j][i]
。
感觉和分段 dp 有点像。
话说我又忘赋初值了/xk
#include
using namespace std;
char a[201],b[201];
int n;
int f[201][201],g[201];
int main()
{
scanf("%s%s",a+1,b+1);
n=strlen(a+1);
for(int i=1;i<=n;i++)//上道题的做法
{
g[i]=2e9;
for(int j=1;j<=n;j++) f[i][j]=2e9;
}
for(int i=1;i<=n;i++) f[i][i]=1;
for(int l=2;l<=n;l++)
{
for(int i=1;i<=n-l+1;i++)
{
int j=i+l-1;
for(int k=i;k
真的好难想啊qwq