UVa11552 Fewest Flops(普通动态规划)

刚开始的想法是$dp(i,j,k)$表示到第$i$个块,开头为$i$,结尾为$j$的最小的$chunk$数,然后发现这样做要讨论该块是否只有一个这个字母,如果不是还要看一块的开头和结尾是不是相同字母,如果还不是再去与前面的块比较,写完的时候就是几个循环套几个循环了,复杂度有点危险并且WA了,代码极丑我就不发了。然后去看题解,发现有简单的多的状态表示以及递推,我为什么就没想到呢…

设$dp(i,j)$为到第$i$个块,结尾为$j$的最小$chunk$数,然后就可以递推了。设$blocksum(i)$为第$i$块的不同字符个数

$$dp(i,j)=min(dp(i-1,k)+blocksum(i)-1), if~ k ~\in block_i$$

$$dp(i,j)=min(dp(i-1,k)+blocksum),if~ k~ \in block(i-1)$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
const int inf=0x3f3f3f3f;
set<int> rfl[maxn];
char s[maxn];
int dp[maxn][26];
int par,kas,bs;
int main()
{
scanf("%d",&kas);
for(int z=0;z<kas;z++)
{
scanf("%d%s",&par,s);
for(int i=0;i<maxn;i++) rfl[i].clear();
int len=strlen(s);
bs=len/par;
for(int i=0;i<bs;i++)
for(int j=0;j<par;j++)
rfl[i].insert(s[i*par+j]-'a');
memset(dp,inf,sizeof(dp));
for(int i=0;i<26;i++)
if(rfl[0].count(i)) dp[0][i]=rfl[0].size();
for(int i=1;i<bs;i++)
{
int block=rfl[i].size();
for(int j=0;j<26;j++)
{
if(rfl[i].count(j)){
for(int k=0;k<26;k++)
{
if(rfl[i].count(k) && (k!=j || (int)rfl[i].size()==1))
{
dp[i][j]=min(dp[i][j],dp[i-1][k]+block-1);
}
else if(rfl[i-1].count(k)) dp[i][j]=min(dp[i][j],dp[i-1][k]+block);
}
}
}
}
int ans=inf;
for(set<int>::iterator ite=rfl[bs-1].begin();ite!=rfl[bs-1].end();ite++)
{
ans=min(ans,dp[bs-1][*ite]);
}
printf("%d\n",ans);
}
return 0;
}