本文共 1396 字，大约阅读时间需要 4 分钟。
将字符串分为len/k块。用dp[i][j]表示第i个块必须以j结尾的最小划分。当第i块没有字符j时，dp[i][j]多计一个。如果当前块只有1种字符，那么就等于dp[i-1][j]。否则对于第i块的所有元素，以它来连接前一块，dp[i][j]=min(dp[i-1][i块中的元素]+i块元素数量-1)。如果第i块中不存在j元素，多计一个。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define mkp make_pairusing namespace std;const double EPS=1e-8;typedef long long lon;const lon SZ=1010,INF=0x7FFFFFFF,mod=1000000007;int k,len;char ch[SZ];int dp[SZ][30];void init(){ cin>>k>>ch+1; len=strlen(ch+1); int num=len/k; for(int i=0;i<26;++i)dp[0][i]=1; for(int i=1;i<=num;++i) { for(int j=0;j<26;++j)dp[i][j]=INF; int bg=(i-1)*k+1,end=i*k; set st; for(int j=bg;j<=end;++j) { st.insert(ch[j]); } if(st.size()==1) { int cur=*st.begin()-'a'; dp[i][cur]=dp[i-1][cur]; for(int j=0;j<26;++j) { if(j!=cur)dp[i][j]=dp[i-1][cur]+1; } } else { for(auto it=st.begin();it!=st.end();++it) { int cur=*it-'a'; for(int j=0;j<26;++j) { if(j==cur||st.find(j+'a')==st.end()) { dp[i][j]=min(dp[i][j],dp[i-1][cur]+(int)st.size()); } else dp[i][j]=min(dp[i][j],dp[i-1][cur]+(int)st.size()-1); } } } }// for(int i=1;i<=num;++i)// {// for(int j=0;j<26;++j)// {// cout< <<" ";// }cout< >casenum; //cout< < >n>>m,n;++time) { init(); work(); } return 0;}
转载于:https://www.cnblogs.com/gaudar/p/9894478.html