动规题目:字符串S由小写字母构成,长度为n。定义一种操作,每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?参考博客
#include <iostream>
#include <string.h>
#include <algorithm>
#define N 26
using namespace std;
int dp(int i,int j,int a[]){
if(i == j) return 0;
else if(i+1 == j) return a[j]-a[i]-1;
else return dp(i+1,j-1,a)+a[j]-a[i]-(j-i);
}
int main(){
string str;
int num;
cin >> str >> num;
int length = str.length();
int a[length][N];
int b[N];
int m[length];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(m,0,sizeof(m));
for(int i=0;i<length;i++)
for(int j=0;j<N;j++)
a[i][str[i]-'a'] = 1;
for(int j=0;j<N;j++){
int k=0;
for(int i=0;i<length;i++)
if(a[i][j] == 1)
m[k++] = i;
if(k == 1) b[j] = 1;
else if(!k) b[j] = 0;
else{
int temp=-1;
for(int i=0;i<k;i++)
for(int ii=i+1;ii<k;ii++)
if(dp(i,ii,m)<=num && ii-i+1>temp)
temp = (ii-i)+1;
b[j] = temp;
}
}
sort(b,b+N);
cout << b[N-1] << endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)