最小的块数 (Fewest Flops,UVa 11552)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const int INF=0x7fffffff;
14 #define MAXN 1002
15 int dp[MAXN][26][26];
16 string ss[MAXN];
17 string clear(string a)
18 {
19     int hash[26]={0};
20     string b="";
21     for(int i=0;i<a.length();i++)
22     if(hash[a[i]-'a']==0)
23     {
24        hash[a[i]-'a']++;
25        b+=a[i];
26     }
27     return b;
28 }
29 int Find(int e,int b)
30 {
31     for(int i=0;i<ss[e].length();i++)
32     if(ss[e][i]==ss[e+1][b])return i;
33     return -1;
34 }
35 int main()
36 {
37     int T;scanf("%d",&T);
38     int k;
39     string s;
40     while(T--)
41     {
42         scanf("%d",&k);
43         cin>>s;
44         memset(dp,0,sizeof(dp));
45 
46         int len=s.length();
47         int n=len/k;
48         for(int i=0;i<n;i++)
49         {
50             ss[i]=clear(s.substr(i*k,k));
51             //cout<<ss[i]<<endl;
52         }
53 
54         for(int i=0;i<n;i++)
55         {
56             for(int b=0;b<ss[i].length();b++)
57             for(int e=0;e<ss[i].length();e++)
58             {
59                 dp[i][b][e]=INF;
60                 if(b!=e||ss[i].length()==1)
61                 {
62                     if(i==0)dp[i][b][e]=ss[i].length();
63                     else
64                     {
65                         int pos=Find(i-1,b);
66                         int temp;
67                         if(pos!=-1)
68                         {
69                             temp=INF;
70                             for(int j=0;j<ss[i-1].length();j++)
71                             {
72                                 temp=min(temp,dp[i-1][j][pos]);
73                             }
74                             dp[i][b][e]=temp+ss[i].length()-1;
75                         }
76                         temp=INF;
77                         for(int x=0;x<ss[i-1].length();x++)
78                         for(int y=0;y<ss[i-1].length();y++)
79                             temp=min(temp,dp[i-1][x][y]);
80                         dp[i][b][e]=min(dp[i][b][e],temp+(int)ss[i].length());
81                     }
82                 }
83             }
84         }
85         int ans=INF;
86         for(int b=0;b<ss[n-1].length();b++)
87         for(int e=0;e<ss[n-1].length();e++)
88         ans=min(ans,dp[n-1][b][e]);
89         printf("%d
",ans);
90     }
91     return 0;
92 }
dp[i][b][e] 表示第i个分组以b字母开头且以e字母结尾时前i个分组的最小划分数。