校招笔试题1

校招笔试题1

【编码题】字符串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连续出现。

#include <iostream>
#include <string>
#include <fstream>
#include <array>
#include <vector>
#include <algorithm>
#include <sstream>
#include <numeric>
#include <iterator>
#include <map>
#include <memory>using namespace std;int dp(int i, int j, vector<int> &p, map<pair<int, int>, int> &memo)
{if (memo.find(make_pair(i, j)) != d()){return memo[make_pair(i, j)];}if (i == j){memo[make_pair(i, j)] = 0;return 0;}else if (i + 1 == j){memo[make_pair(i, j)] = p[j] - p[i] - 1;return p[j] - p[i] - 1;}else{int temp = dp(i + 1, j - 1, p, memo) + ((p[j] - p[i] - 1) - (j - i - 1));memo[make_pair(i, j)] = temp;return temp;}
}int main()
{vector<vector<int>> record(26, vector<int>(0));string s;int m;cin >> s >> m;for (int i = 0; i < s.size(); ++i){record[s[i] - 'a'].push_back(i);}int maximum = -1;for (vector<int> & v : record){map<pair<int, int>, int> memo;int size = v.size();for (int i = 0; i < size; ++i){for (int j = i + 1; j < size; ++j){int t = dp(i, j, v, memo);if (t <= m){if ((j - i + 1) > maximum){maximum = (j - i + 1);}}}}}cout << maximum << endl;// system("pause");return 0;
}