我有个大胆的想法不知道对不对，长度为1的情况下没法换，长度为2的情况下最多换1一次，3最多换3次$(cba)$，4最多换6次，在长度小于等于26的情况下最多换$1+2+..+26$次,在长度大于26的情况下没多一个字母可以增添$26$次,根据这个应该就能写了吧。
by 星空舞涵 @ 2021-02-27 08:53:35
最多换$1+2+...+25$次，上面打错了，每次也是增添$25$
by 星空舞涵 @ 2021-02-27 08:54:38
@[星空舞涵](/user/243750) 这个可以算出答案对应的长度，但是如果要算出具体字符串的做法怎么弄呀
by CodyTheWolf @ 2021-02-27 11:48:31
@[星空舞涵](/user/243750) 26个以后应该不是增添25个，例如26 ~ 52 ，长度为 L 增加到 L + 1，应该是增加 L - 1 个 （不一样的字母有L - 1个，且都能成逆序对）
by CodyTheWolf @ 2021-02-27 11:54:52
写出来了，跟原题解不一样在于舍弃了f数组，直接计算chcnt数组（在我这就是dp数组）
DP
- $dp[i][j]$ 表示 长度为 i 的 且以 字母('a' + j - 1) 开头的字符串，最大逆序对数量
- 转移的话枚举 k < i 那么从上个字母转移到现在增加的逆序对就是 k * (i - k)
构造字符串
- 找出 i 最小，其次 j 最小的，并且dp[i][j] >= 0 的 i , j
- 从长为 i ，以字母('a' + j - 1)开头，分三种情况讨论
- - 如果j == 1，就不能令字典序再小了，只能输出'a'
- - 如果dp[i][j - 1] >= v 说明当前字符可以变小而且变小后，后面的字符串仍然可以凑足逆序对数，剩下要凑的逆序对为 v - (i - 1)
- - 否则此时不能换字符，只能延续，剩下要凑的逆序对为 v - (i - 1) + same (v -= i - 1 - same)
这里的MAXN * (MAXN - 1) == v
所以复杂度大概为O(26v)
```
#include <iostream>
#include <cstring>
using namespace std;
constexpr size_t MAXN = 5e3;
int dp[MAXN][27];
int v;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
memset(dp, 0x80, sizeof dp), dp[0][0] = 0;
cin >> v;
for (int i = 1; i < MAXN; i++)
for (int j = 1; j <= 26; j++)
for (int k = 0; k < i; k++)
dp[i][j] = max(dp[i][j], dp[k][j - 1] + k * (i - k));
int i = 0, j = 0, same = 0, flag = 1;
while (flag) {
j = 1, i++;
for (; j <= 26; j++) {
if (dp[i][j] >= v) { flag = 0; break; }
}
}
while (i) {
if (j == 1)
cout << (char)'a';
else if (dp[i][j - 1] >= v)
j--, cout << (char)(j + 'a' - 1), v -= i - 1, same = 1;
else
cout << (char)(j + 'a' - 1), v -= i - 1 - same, same++;
i--;
}
}
```
by CodyTheWolf @ 2021-02-27 14:00:12
前排orz
by 血虎之爪 @ 2021-03-04 15:51:42