正题

---

大意

先给出n个句子，然后给出一个最终句子。最终句子由多个句子加密后组成（可能重复）。加密方法就是将字母调换位置，加密代价就是该位置与原来的字母不同的数量。求达到最终句子的最小加密代价

---

解题思路

用f[i]f[i]表示最终句子已经完成了前i个单词的最小代价，枚举加密用的句子，然后列出动态转移方程：

f[i]=f[i−len[j]]+wf[i]=f[i−len[j]]+w
w为该段支付的加密代价。

---

代码

#include<cstdio> #include<string> #include<iostream> using namespace std; int n,al,l[51],t[26],w,f[101]; string s[51],ans; int main() {scanf("%d",&n);for (int i=1;i<=n;i++){cin>>s[i];l[i]=s[i].size();}cin>>ans;al=ans.size();for (int i=1;i<=al;i++){f[i]=214748364;for (int j=1;j<=n;j++){if (i<l[j]) continue;for (int k=0;k<26;k++) t[k]=0;//桶w=0;for (int k=0;k<l[j];k++){if (ans[i-l[j]+k]!=s[j][k]) w++;//代价t[int(ans[i-l[j]+k])-97]++;t[int(s[j][k])-97]--;}for (int k=0;k<26;k++)if (t[k]) {w=214748364;break;//无法连接}f[i]=min(f[i],f[i-l[j]]+w);//动态转移}}if (f[al]==214748364) printf("-1");//无解else printf("%d",f[al]);//输出 }

总结

以上是生活随笔为你收集整理的【2018.3.31】模拟赛之四-ssl2408 句子【dp,字符串】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。