题目描述:
/**
【编码题】
字符串S由小写字母构成,长度为n。定义一种操作,
每次都可以挑选字符串中任意的两个相邻字母进行交换。
询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?
输入描述:
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)
输出描述:
一个非负整数,表示操作之后,连续最长的相同字母数量。
输入例子1:
abcbaa 2
输出例子1:
2
例子说明1:
使2个字母a连续出现,至少需要3次操作。即把第1个位置上的a移动到第4个位置。
所以在至多操作2次的情况下,最多只能使2个b或2个a连续出现。
*/
思路如下:
维护一个表每个
每行存放同样字符之间的位置(按原来顺序摆放)
在位置向量中
dp[i][j] = dp[i+1][j-1] + abs(posVec[j] - posVec[i]) - (j-i);
dp[i][j]第i个数->第j个数移动的次数
base case:
dp[i][i]=0
dp[i][i+1]= abs(posVec[i+1] - posVec[i]) - 1
i<=j
这里只枚举i<=j是因为 j<=i时候其实是对称的情况
代码如下:
#include<stdio.h>
#include<iostream>
#include<vector>
#define MAX_ROW 26
using namespace std;
vector<int> posTable[MAX_ROW];
int DP(const vector<int> &posVec, int K)
{
int n = posVec.size();
vector< vector<int> > dp(n, vector<int>(n, 0));
for(int i=0; i<n-1; ++i)
{
dp[i][i+1] = abs(posVec[i+1] - posVec[i]) - 1;
}
for(int j=2; j<n; ++j)
{
for(int i=0; i<n-j; ++i)
{
int row = i, col = i+j;
dp[row][col] = dp[row+1][col-1] + abs(posVec[col] - posVec[row]) - (col-row);
}
}
int Max = 0;
for(int i=0; i<n; ++i)
{
for(int j=i; j<n; ++j)
{
if (dp[i][j] <= K)
{
Max = max(Max, j-i+1);
}
}
}
return Max;
}
int main()
{
//建立posTable;
string line;
int K;
cin>>line>>K;
for(int i=0; line[i]!='\0'; i++)
{
if(line[i]<'a' || line[i]>'z')
return -1;
posTable[line[i]-'a'].push_back(i);
}
//找最大滑动窗口
int maxSize=0;
for(int i=0; i<MAX_ROW; i++)
{
vector<int> &pos=posTable[i];
maxSize=max(maxSize, DP(pos, K));
}
printf("%d", maxSize);
return 0;
}