Problem Description
When you arrived at Charles de Gaulle airport, you naively accepted a ride to Paris by an unauthorized driver who offered you “competitive prices”. The end result was a disaster: not only was the price extremely high, but the driver made the trip much longer than necessary in order to justify that price.
You noticed the scam because you were traveling several times by the same place: indeed, you have such a good memory that you can remember very well the path you followed, including each of the loops that your scammer forced you to take.
Now, you are at the police station to fill a complaint against this driver and an officer asks you to tell your story. She even asks you to give all the details of the path you took. Because you do not want to lose yet another couple of hours in doing so, you decide to give a compressed version of it.
Suppose you remember you traveled through places A, B, C, D, A, B, C, D. In this case, you prefer telling the officer “I followed twice the path ABCD”, rather than “I followed the path ABCDABCD”. Given that your path repeated the same sequence of places, this will significantly shorten your statement, without missing any detail.
More precisely, you have to write a program that takes as input the list of places you traveled through, and which returns the size of the shortest compressed form of this path. Such a compressed path can either be:
-
a single place through which you traveled, called an “atomic path”;
-
the concatenation of two compressed paths;
-
the repetition of a compressed path, i.e., (C)n, meaning that you traveled through the path described by C, n times in a row.
The size of a compressed path is defined as the number of atomic paths it contains.
Input
5 test cases and for each case:
The input consists of two lines:
-
The first line contains one integer, N, the length of the path.
-
The second line contains the path, described as a string of size N. Each location is described by an alphanumeric character: either a digit (from ‘0’ to ‘9’), a lowercase letter (from ‘a’ to ‘z’) or an uppercase letter (from ‘A’ to ‘Z’).
Output
For each test case:
The output should consist of a single line, whose content is an integer, the size of the shortest compressed path.
Sample Explanation 1
The shortest compressed form of the path is (((a)3b)2(c)2d)2. The atomic paths it contains are a, b, c and d. Hence, it has size 4.
Sample Explanation 2
The shortest compressed form of the path is (a)2ba. The atomic paths it contains are a, b, and a. Hence, it has size 3.
Sample Input
22aaabaaabccdaaabaaabccd
4
aaba
Sample Output
43
题目大意
给出你一个长度为n的字符串，将字符串中重复的连续字符子串压缩，例如将ababab 压缩成（ab）3，问最少可以用多少个字符来表示字符串（数字省略）
题解
首先分析一下题目，如果一个字符子串（长度为len）可以被压缩，那么肯定存在一个该字符串的子串（长度为k）使得k*x=len，即len%k==0，
如果一个字符串不可以被压缩，那么肯定不存在上述子串，那么我们可以将该字符串分成两个子串，而该字符串最少能被压缩的长度就是两个子串的压缩长度的和
由此我们根据上述两点可以得到动态规划的递推公式
f[i][j]表示区间i-j的被压缩后最少压缩成几个字符
初始状态显然是f[i][i]=1;
由第一个推断可以知道转移状态为f[i][j]=min{f[i][j],f[i][i+len-1]} (j-i+1)%len==0 && 子串中i到i+len-1等于i+len到i+2*len-1等于i+2*len到i+3*len-1 等等
由第二个推断可以知道 转移状态为f[i][j]=min{f[i][j],f[i][k]+f[k+1][j]} i<=k<j
答案保存在f[1][n]中
1 #include<bits/stdc++.h>
2 using namespace std;
3 int f[710][710];
4 int len;
5 char s[1000];
6 bool check(int l1,int l2,int len){
7 for (int i=1;i<=len;i++)
8 if (s[l1+i-1]!=s[l2+i-1]) return 0;
9 return 1;
10 }
11 bool check1(int l,int len,int k){
12 for(int i=1;i<k;i++)
13 if (!check(l,l+i*len,len)) return 0;
14 return 1;
15 }
16 int main(){
17 while (cin>>len){
18 cin>>s+1;
19 for (int i=0;i<710;i++)
20 for (int j=0;j<710;j++)
21 f[i][j]=2147483647;
22 for (int i=1;i<=len;i++)
23 f[i][i]=1;
24 for (int i=2;i<=len;i++){
25 for (int j=1;j<=len && j+i-1<=len;j++){
26 for (int xxx=1;xxx<i;xxx++)
27 if (i%xxx==0){
28 if (check1(j,xxx,i/xxx)){
29 f[j][j+i-1]=min(f[j][j+xxx-1],f[j][j+i-1]);
30 }
31 }
32 for(int k=j;k<j+i-1;k++)
33 f[j][j+i-1]=min(f[j][j+i-1],f[j][k]+f[k+1][j+i-1]);
34 }
35 }
36 cout<<f[1][len]<<endl;
37 }
38 }