?

題目傳送門

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

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的多维DP UVA 11552 Fewest Flop的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。