「NOIP模拟赛」秘密文件
「问题描述」
某天，情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长，则需要很长的发送时间，太不安全了，因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则：若一个字符串t连续出现k次，则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然，重复缩短是允许的，如ABABABAAAAAAARABABAAAAAA可以缩成2(3(AB)6(A))
现在，小明想知道，对于给定的字符串，最短可以缩成什么样子。
「输入格式」
输入仅一行，为给定的字符串。
「输出格式」
输出仅一行，为经过缩短操作后的字符串。
若有多解，输出任意解即可。
「样例输入」
AAAAAAAAAARABABCCD
「样例输出」
9(A)3(AB)CCD
「数据范围」
对于l00%的数据，字符串的长度L≤100。
题解
此题是scoi字符串折叠加强版。。。
输出的是方案
我们只要定义一个string ans[i][j]存下i到j最优解的字符串就行了
合并啥的都很简单。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char s[105]; int f[105][105]; string ans[105][105]; bool mark[105][105]; bool jud(int l,int r,int cl,int cr) { if((r-l+1)%(cr-cl+1)!=0)return 0; for(int i=l;i<=r;i++) if(s[i]!=s[(i-l)%(cr-cl+1)+cl])return 0; return 1; } int get(int x) {int t=0;while(x){x/=10;t++;}return t;} string getch(int x) { string tmp; while(x) { tmp=char(x%10+'0')+tmp; x/=10; } return tmp; } int dp(int l,int r) { if(mark[l][r])return f[l][r]; if(l==r){ans[l][r]=s[l];return 1;} mark[l][r]=1; int t=r-l+1; for(int i=l;i<=r;i++)ans[l][r]+=s[i]; for(int i=l;i<r;i++) { int tmp=dp(l,i)+dp(i+1,r); if(tmp<t){t=tmp;ans[l][r]=ans[l][i]+ans[i+1][r];} if(jud(i+1,r,l,i)) { int tmp=dp(l,i)+2+get((r-i)/(i-l+1)+1); if(tmp<t) { t=tmp; ans[l][r]=getch((r-i)/(i-l+1)+1)+"("+ans[l][i]+")"; } } } return f[l][r]=t; } int main() { //freopen("cipher.in","r",stdin); //freopen("cipher.out","w",stdout); scanf("%s",s); int l=strlen(s); dp(0,l-1); cout<<ans[0][l-1]; return 0; } |
Subscribe
计数器 9790074
OI 课件=>
OI 课件=>