UVa 11552 Fewest Flops

dp[m][i][j]代表第m组以字母(i +'a') 开头和以字母 ( j + 'a' )结尾的最小块数。kuai[m]中存储了第 m 组最少可以分为多少块，显然最少为所有相同字母放在一起时的块数，即这一组中不同字母的个数。

如果前一组的结尾与后一组的开头相同，则dp[m][i][j] = min( dp[m-1][st][ed] + kuai[m] - 1 );

若不同，则dp[m][i][j] = min(dp[m - 1][st][ed] + kuai[m] );

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 1010;
 9 const int INF = 1 << 30;
10 
11 char str[MAXN];
12 int dp[MAXN][30][30];
13 int kuai[MAXN];       //记录每组之中最小的块数
14 bool vis[MAXN][30];   //记录每组出现了哪些字母
15 int K, n;
16 
17 void GetKuai()     //预处理得到每组内最小的块数
18 {
19     memset( vis, false, sizeof(vis) );
20     for ( int i = 0; i < n; ++i )
21     {
22         int st = K * i;
23         int ed = K * (i + 1);
24         for ( int j = st; j < ed; ++j )
25             vis[i][ str[j] - 'a' ] = true;
26 
27         kuai[i] = 0;
28         for ( int j = 0; j < 26; ++j )
29             if ( vis[i][j] ) ++kuai[i];
30     }
31     return;
32 }
33 
34 void init()     //初始化
35 {
36     for ( int i = 0; i < 26; ++i )
37         for ( int j = 0; j < 26; ++j )
38             if ( vis[0][i] && vis[0][j] )
39                 dp[0][i][j] = kuai[0];
40             else dp[0][i][j] = INF;
41     return;
42 }
43 
44 void solved()
45 {
46     init();
47 
48     for ( int m = 1; m < n; ++m )
49         for ( int i = 0; i < 26; ++i )
50         {
51             if ( vis[m][i] )
52             {
53                 for ( int j = 0; j < 26; ++j )
54                 {
55                     dp[m][i][j] = INF;
56                     if ( ( j == i && kuai[m] == 1 ) || ( j != i && vis[m][j] ) ) // 这里WA了两次，首位字母不能相同，除非这一组内的块数为1
57                     {
58                         for ( int st = 0; st < 26; ++st )
59                             if ( vis[m - 1][st] )
60                             {
61                                 for ( int ed = 0; ed < 26; ++ed )
62                                 {
63                                     if ( ( st == ed && kuai[m - 1] == 1 ) || ( ed != st && vis[m - 1][ed] ) )
64                                     {
65                                         if ( ed == i )
66                                             dp[m][i][j] = min( dp[m][i][j], dp[m - 1][st][ed] + kuai[m] - 1 );
67                                         else dp[m][i][j] = min( dp[m][i][j], dp[m - 1][st][ed] + kuai[m] );
68                                     }
69                                 }
70                             }
71                     }
72                 }
73             }
74         }
75 
76     int ans = INF;
77     for ( int i = 0; i < 26; ++i )
78         for ( int j = 0; j < 26; ++j )
79             if ( vis[n - 1][i] && vis[n - 1][j] )
80                 ans = min( ans, dp[n - 1][i][j] );
81 
82     printf( "%d\n", ans );
83     return;
84 }
85 
86 int main()
87 {
88     int T;
89     scanf( "%d", &T );
90     while ( T-- )
91     {
92         scanf( "%d%s", &K, str );
93         n = strlen(str) / K;   //得到块数
94         GetKuai();
95         solved();
96     }
97     return 0;
98 }