题目地址:http://vjudge.net/problem/UVA-11552
hhh,自己写出来了
1.状态如何表示:
要达到两种目的:1)能记录该祖中有几块,2)每组中的字母有几个
我选择用 s[i][j] 表示 i组中,j+'a'+1字母有几个,特别的,用s[i][0]记录i组中有几块
2.状态方程怎么定义,怎么转移
肯定有一维i表示在第几组,因为每次选字母时和前面最后的字母有关,所以j表示以j字母为结尾
那么 d[i][j] 表示 1~i组中 ,且第i组以j字母结尾 ,最小的分块数
转移:
d[i][j]=min{d[i-1][k]+s[i][0]-(s[i][k]>0?1:0)}
注意 : k!=j,除非i组中字母都是j
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int maxn=1000+5,INF=0x3f3f3f3f;
char str[maxn];
int s[maxn][27],d[maxn][27];
int main(int argc, char const *argv[])
{int T,n; scanf("%d",&T);while(T--&&scanf("%d",&n)==1){scanf("%s",str);int len=strlen(str),nGroup=len/n;memset(s,0,sizeof(s));REP(i,0,len-1){int idx=i/n+1;if(s[idx][str[i]-'a'+1]==0) s[idx][0]++;s[idx][str[i]-'a'+1]++;}memset(d,INF,sizeof(d));REP(i,1,26) if(s[1][i]) d[1][i]=s[1][0];REP(i,2,nGroup) {REP(j,1,26) if(s[i][j]){REP(k,1,26) if(s[i-1][k]) {if(j==k&&s[i][j]!=n) continue; //j!=k 除非 i Group全是一个字母jd[i][j]=min(d[i][j],d[i-1][k]+s[i][0]-(s[i][k]?1:0));}}}int ans=INF;REP(i,1,26) if(s[nGroup][i]) ans=min(ans,d[nGroup][i]);printf("%d\n", ans);}return 0;
}