多維DP UVA 11552 Fewest Flop

題目傳送門

 1 /*
 2     題意：將子符串分成k組，每組的字符順序任意，問改變后的字符串最少有多少塊
 3     三維DP：可以知道，每一組的最少塊是確定的，問題就在于組與組之間可能會合并塊，總塊數會-1。
 4         dp[i][j]表示第i組以第j個字符結尾的最少塊數，狀態轉移方程：dp[i][j] = min (dp[i][j], dp[i-1][l] + chunk - 1);
 5         意思就是枚舉上一組的所有字符，當出現在i組并且不是放到末尾，那么能-1
 6 */
 7 /************************************************
 8 * Author        :Running_Time
 9 * Created Time  :2015-8-7 11:08:46
10 * File Name     :UVA_11552.cpp
11  ************************************************/
12 
13 #include <cstdio>
14 #include <algorithm>
15 #include <iostream>
16 #include <sstream>
17 #include <cstring>
18 #include <cmath>
19 #include <string>
20 #include <vector>
21 #include <queue>
22 #include <deque>
23 #include <stack>
24 #include <list>
25 #include <map>
26 #include <set>
27 #include <bitset>
28 #include <cstdlib>
29 #include <ctime>
30 using namespace std;
31 
32 #define lson l, mid, rt << 1
33 #define rson mid + 1, r, rt << 1 | 1
34 typedef long long ll;
35 const int MAXN = 1e3 + 10;
36 const int INF = 0x3f3f3f3f;
37 const int MOD = 1e9 + 7;
38 char str[MAXN];
39 int dp[MAXN][MAXN];
40 bool vis[130];
41 
42 int main(void)    {     //UVA 11552 Fewest Flop
43     int T;  scanf ("%d", &T);
44     while (T--) {
45         int k;  scanf ("%d%s", &k, str + 1);
46         int len = strlen (str + 1);
47         memset (dp, INF, sizeof (dp));
48         for (int i=1; i<=len/k; ++i)    {
49             memset (vis, false, sizeof (vis));
50             for (int j=(i-1)*k+1; j<=i*k; ++j)  {
51                 vis[str[j]] = true;
52             }
53             int chunk = 0;
54             for (int j='a'; j<='z'; ++j)    {
55                 if (vis[j])    chunk++;
56             }
57             if (i == 1) {
58                 for (int j=1; j<=k; ++j)    {
59                     dp[i][j] = chunk;
60                 }
61                 continue;
62             }
63             for (int j=1; j<=k; ++j)    {
64                 int last = (i - 1) * k + j;
65                 for (int l=1; l<=k; ++l)    {
66                     int pre = (i - 2) * k + l;
67                     if (vis[str[pre]] && (chunk == 1 || str[pre] != str[last]))  {
68                         dp[i][j] = min (dp[i][j], dp[i-1][l] + chunk - 1);
69                     }
70                     else    dp[i][j] = min (dp[i][j], dp[i-1][l] + chunk);
71                 }
72             }
73         }
74 
75         int ans = INF;
76         for (int i=1; i<=k; ++i)    {
77             ans = min (ans, dp[len/k][i]);
78         }
79         printf ("%d\n", ans);
80     }
81 
82     return 0;
83 }

轉載于:https://www.cnblogs.com/Running-Time/p/4711104.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/397704.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/397704.shtml
英文地址，請注明出處：http://en.pswp.cn/news/397704.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！