codeforces 1003 F Abbreviation

codeforces 1003 F Abbreviation

​​ 题意：缩小一次之后最小的长度缩小为多少

那么我是直接暴力做的.. 考虑首先先把每个字符串变成数字 然后暴力枚举区间

然后贪心的看和这个区间相同的最多有多少个 那么 找出之后计算答案看能否更新即可

#includeusing namespace std;const int N=330;int n,s[N],id[N],cnt,ans;map mm;int main(){// freopen("f.in","r",stdin); std::ios::sync_with_stdio(false); cin>>n; for (int i=1;i<=n;++i){ string tmp;cin>>tmp;int idd=0; if(!mm[tmp]) mm[tmp]=idd=++cnt;else idd=mm[tmp]; id[i]=idd;s[i]=s[i-1]+tmp.length(); }ans=s[n]+n-1; for (int i=1;i<=n;++i){ for (int j=i;j<=n;++j){ int d=j-i,tot=0; for (int k=j+1;k+d<=n;++k){ bool flag=1; for (int z=0;z<=d;++z) if (id[i+z]!=id[k+z]){flag=0;break;} if (flag) ++tot,k+=d; } if(tot){ int tmp=s[n]-(tot+1)*(s[j]-s[i-1])+tot+n; ans=min(ans,tmp); } } }printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。