首页 > 代码库 > uva11552

uva11552

2024-07-28 12:44:24   218人阅读

题意: 给一个长度为n的串n<1000然后将这个串平均分成k分,分别为 s1 s2 s3...sk,这k份中可以任意的交换字母位置 比如uuvuwwuv 切成两份 这样 uuvu 和wwuv 这样然后 重新整理一下就得到了 uuuv 和vuww 这样合并uv和vuw 在将两个合并 得到 uvuw 为4 个能在消的字符，问最后最小的结果是多少。刚开始考虑 交换他们的不同匹配，因为只要考虑两端就行了，贪心的进行交换结果wa了， 考虑dp[i][c]表示在第i部分的末尾放c的最小值，特判只有1种的情况 然后其他的 不能自己当头又当尾就行了 从前一个状态转移而来 如果有相同的就 +len[i]-1 否则就 +len[i]

dp[i][c]=min(dp[i-1][j]+v)j!=c 特判 1  ，v= i中有没有j ?len[i]-1:len[i];

#include <iostream>#include <cstdio>#include <string.h>#include <vector>using namespace std;const int maxn = 1005;int dp[maxn][30];int ch[maxn][30];int len[maxn];vector<int> common[maxn];char str[maxn];int k,num;void inti(int n ){     for(int i=0; i<=n; ++i)         for(int j=0; j<26; ++j)           dp[i][j]=maxn;}int main(){     int cas;     scanf("%d",&cas);     for(int cc=1; cc<=cas; ++cc){         scanf("%d%s",&k,str);         int L = strlen(str);         num=1;         for(int i=0; i<L; i+=k){            len[num]=0;            memset(ch[num],0,sizeof(ch[num]));            for(int j=i; j<i+k; ++j) ch[num][str[j]-‘a‘]=1;            common[num].clear();            for(int j=0; j<26; ++j)                if(ch[num][j]==1){                     common[num].push_back(j);                     len[num]++;                }            num++;        }        inti(num);        for(int i=0; i<common[1].size(); ++i)            dp[1][common[1][i]]=len[1];        for(int i=2; i<num; ++i){            int sz=len[i];            if(sz==1){                int t=common[i][0];                for(int j=0; j<26; ++j)                    if(t==j) dp[i][t]=min(dp[i][t],dp[i-1][j]+sz-1);                    else dp[i][t]=min(dp[i][t],dp[i-1][j]+sz);            }else {                for(int j=0; j<26; ++j)                   for(int d=0; d<sz; ++d){                       int t=common[i][d];                       if(ch[i][j]==1&&t!=j)                            dp[i][t]=min(dp[i][t],dp[i-1][j]+sz-1);                       if(ch[i][j]==0) dp[i][t]=min(dp[i][t],dp[i-1][j]+sz);                   }            }        }        int ans=maxn;        for(int i=0; i<26; ++i)            ans=min(ans,dp[num-1][i]);        printf("%d\n",ans);     }    return 0;}
View Code

 

uva11552


联系
我们