本文主要是介绍UVA 11552 Fewest Flops,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
水题
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAX 1100
using namespace std;char s[MAX];
int L,k,dp[MAX][26],count_t[26];void init(){cin>>k;cin>>s;L=strlen(s);memset(dp,0x7f,sizeof(dp));
}void solve(){for(int i=0;i<L/k;i++){int front=i*k,rear=(i+1)*k-1;memset(count_t,0,sizeof(count_t));for(int j=front;j<=rear;j++)count_t[s[j]-'a']++;int kind=0;for(int j=0;j<26;j++)if(count_t[j])kind++;for(int j=0;j<26;j++){if(count_t[j]){if(i==0)dp[i][j]=kind;else{for(int t=0;t<26;t++){if(j!=t){if(count_t[t])dp[i][j]=min(dp[i][j],dp[i-1][t]+kind-1);elsedp[i][j]=min(dp[i][j],dp[i-1][t]+kind);}else{if(kind==1)dp[i][j]=min(dp[i][j],dp[i-1][t]);elsedp[i][j]=min(dp[i][j],dp[i-1][t]+kind);}}}}}}int ans=0x7f7f7f7f;for(int i=0;i<26;i++){ans=min(ans,dp[L/k-1][i]);}cout<<ans<<endl;
}int main(){int T;cin>>T;while(T--){init();solve();}return 0;
}
这篇关于UVA 11552 Fewest Flops的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!