SSL 2409 句子#线性动态规划#

本文主要是介绍SSL 2409 句子#线性动态规划#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

比赛

---

题目

---

分析

dp
状态转移方程：

$f[i]$表示加密后的单词$1-i$的最小代价

$f[i]=\min (f[i],f[i-len[j]]+w)$

---

代码

#include <cstdio>
#include <cstring>
#include <climits>
using namespace std;
int n,len[51],slen,alpha[26],f[101]; char s[102],word[51][52];
int main(){freopen("sents.in","r",stdin);freopen("sents.out","w",stdout);scanf("%d\n",&n);for (int i=1;i<=n;i++) scanf("%s",word[i]+1),len[i]=strlen(word[i]+1);scanf("%s",s+1); slen=strlen(s+1);for (int i=1;i<=slen;i++){f[i]=INT_MAX;for (int j=1;j<=n;j++){if (i<len[j]) continue; //不可能转换int w=0;memset(alpha,0,sizeof(alpha));for (int k=1;k<=len[j];k++){if (s[i-len[j]+k]!=word[j][k]) w++;//需要转换alpha[s[i-len[j]+k]-97]++;//增加alpha[word[j][k]-97]--;//减少}for (int k=0;k<26;k++) if (alpha[k]) w=INT_MAX;//如果出现不能解码的自动无解if ((long long)f[i-len[j]]+w<f[i]) f[i]=f[i-len[j]]+w;//动态规划}}if (f[slen]!=INT_MAX) printf("%d",f[slen]); else puts("-1");
}

这篇关于SSL 2409 句子#线性动态规划#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---