传送门 一道挺妙的区间dp.
我们先用区间dp求出第一个串为空串时的最小代价。 然后再加入原本的字符更新答案就行了。 代码：
#include<bits/stdc++.h>
using namespace std
;
char s
[105],t
[105];
int n
,ans
[105],f
[105][105];
inline int dfs(int l
,int r
){
if(~f
[l
][r
])return f
[l
][r
];
if(l
==r
)return f
[l
][r
]=1;
f
[l
][r
]=0x3f3f3f3f;
for(int mid
=l
;mid
<r
;++mid
)f
[l
][r
]=min(f
[l
][r
],dfs(l
,mid
)+dfs(mid
+1,r
));
if(t
[l
]==t
[r
])f
[l
][r
]=min(f
[l
][r
],dfs(l
+1,r
));
return f
[l
][r
];
}
int main(){
while(~scanf("%s%s",s
+1,t
+1)){
n
=strlen(s
+1);
memset(f
,-1,sizeof(f
));
for(int i
=1;i
<=n
;++i
){
ans
[i
]=dfs(1,i
);
for(int j
=1;j
<i
;++j
)ans
[i
]=min(ans
[i
],ans
[j
]+dfs(j
+1,i
));
if(s
[i
]==t
[i
])ans
[i
]=min(ans
[i
],ans
[i
-1]);
}
cout
<<ans
[n
]<<'\n';
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-4932224.html
