2009年南海初中竞赛 句子

2009年南海初中竞赛 句子

题目

解题思路

动态规划，动态规划转移方程为f[i]=min(f[i],f[i-q[j]]+gg); 其中q[j]为当前字符串的长度，gg为代价。

寻找代价的过程，可以用桶来完成。

代码

#include<cstdio>
#include<iostream>
#include<string>
using namespace std; 
const int inf=100000000; 
int n,f[101],q[101],qq,tg[30]; string s[101],g; 
int main()
{scanf("%d",&n); for (int i=1;i<=n;i++)cin>>s[i],q[i]=s[i].size(); cin>>g; qq=g.size();for (int i=1;i<=qq;i++){f[i]=inf; //初始化for (int j=1;j<=n;j++){if (i<q[j]) continue; for (int k=0;k<26;k++) tg[k]=0; //桶的初始化int gg=0; for (int k=0;k<q[j];k++){if (g[i-q[j]+k]!=s[j][k]) gg++; tg[g[i-q[j]+k]-97]++; tg[s[j][k]-97]--; //如果可以转化的话，就会相互抵消}for (int k=0;k<26;k++)if (tg[k]) {gg=inf; break; }//否则给gg赋一个无穷大值f[i]=min(f[i],f[i-q[j]]+gg); //动态规划}}if (f[qq]==inf) printf("-1"); else printf("%d",f[qq]);//判断是否无解
}