本文主要是介绍UVA11552——Fewest Flops（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
FEWEST FLOPS
A common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of times the character occurs followed by the character itself. For example, the string “aabbbaabaaaa” may be encoded as “2a3b2a1b4a”. (Note for this problem even a single character “b” is replaced by “1b”.)
Suppose we have a string S and a number k such that k divides the length of S. Let S1 be the substring of S from 1 to k, S2 be the substring of S from k + 1 to 2k, and so on. We wish to rearrange the characters of each block Si independently so that the concatenation of those permutations S’ has as few chunks of the same character as possible. Output the fewest number of chunks.
For example, let S be “uuvuwwuv” and k be 4. Then S1 is “uuvu” and has three chunks, but may be rearranged to “uuuv” which has two chunks. Similarly, S2 may be rearranged to “vuww”. Then S’, orS1S2, is “uuuvvuww” which is 4 chunks, indeed the minimum number of chunks.
Program Input
The input begins with a line containing t (1 ≤ t ≤ 100), the number of test cases. The following t lines contain an integer k and a string S made of no more than 1000 lowercase English alphabet letters. It is guaranteed that k will divide the length of S.
Program Output
For each test case, output a single line containing the minimum number of chunks after we rearrange Sas described above.
INPUT
2 5 helloworld 7 thefewestflops
OUTPUT
8 10
题意:
给出一个字符串, 并且给出一个k, 并且保证字符串可以分成k段, 每段等长. 每段里面的字符可以任意排列, 但是段与段之间顺序不变, 组合之后要使得字符串里面的块数最少,相同的字符放在一起可以统计为一块, 一个字符也可以单独成块.
分析：
首先串k长度为单位进行预处理，处理出每个单位长度内出现过的字母。因为相同的字母一定是靠在一起的情况下才能块数最少。
dp[i][j] 表示前i个单位长度，以j为结尾的最少的块数。
状态转移方程就是
当第i个单位的首元素与前i-1个结尾元素相同时，即st==j ：
dp[i][ed]=min(dp[i][ed],dp[i-1][j]+x-1);
否则：
dp[i][ed]=min(dp[i][ed],dp[i-1][j]+x);
（其中x是第i个单位内的块数。 st，ed是第i个单位开头和结尾元素。 ）
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#define INF 10000
using namespace std;typedef long long LL;
const int N = 1e5 + 10;vector<int> w[1005];
char s[1005];
int a[30],dp[1005][30];void init()
{for(int i=0; i<1005; i++)for(int j=0; j<26; j++)dp[i][j]=INF;for(int i=0; i<=1000; i++)w[i].clear();
}
int main()
{int T,k;scanf("%d",&T);while(T--){init();scanf("%d %s",&k,s);int len=strlen(s);int cnt=0;for(int i=0; i<len;){memset(a,0,sizeof(a));for(int j=0; j<k; j++,i++)a[s[i]-'a']++;for(int j=0; j<26; j++)if(a[j]) w[cnt].push_back(j);cnt++;}for(int i=0; i<w[0].size(); i++)dp[0][w[0][i]]=w[0].size();for(int i=1; i<cnt; i++){int x=w[i].size();for(int j=0; j<26; j++){for(int p=0; p<x; p++)for(int q=0; q<x; q++){if(p==q&&x!=1) continue;int st=w[i][p];int ed=w[i][q];if(st==j)dp[i][ed]=min(dp[i][ed],dp[i-1][j]+x-1);elsedp[i][ed]=min(dp[i][ed],dp[i-1][j]+x);}}}int ans=INF;for(int i=0; i<26; i++){ans=min(ans,dp[cnt-1][i]);}printf("%d\n",ans);}return 0;
}
这篇关于UVA11552——Fewest Flops（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
