Logo Turtle

Created by LXC on Sat Jun 17 09:40:36 2023

https://codeforces.com/problemset/problem/132/C

ranting: 1800

tag: dp

problem

给出一个长度最多为100的串，其只有T和F两种字符组成。其中T代表反转方向，F代表在此方向上前进一步。

你可以操作n次，每次操作可以让其中一个T变为F或F变为T，可以多次操作同一个位置。

现在问操作n次后，里起点的最大距离是多少。

solution

不断在测试用例中找规律，又被折磨了一下午

虽然通过了，但是这个方法的正确性也有待商榷。

首先进行分类讨论：

对于n大于等于串的长度len，考虑贪心。那么我们可以先让所有T变为F，接下来在最后一个位置上操作剩余次数即可，那么剩余的次数如果是奇数那么答案就是距离len-1，否则距离就是len。

那么对于长度不大于n的话，我们考虑用dp。

在已有的串后面新增一个T，代表哨兵。在加入一个T后设T的总数为tsz

那么串可以表示为$a_1T_1a_2T_2\cdots a_{tsz}T_{tsz}$

其中$a_i$代表第i个T与第i-1个T之间F的个数。

现在定义状态$f_{i,j}$为在前i个T中移除j个T（第i个T不移除，所以$j<i$）所能达到的最大值。由于要计算距离起点的最大距离，所以对于最终的终点可能会落在反方向上，于是定义状态$g_{i,j}$为在前i个T中移除j个T（第i个T不移除）所能达到的最小值。

对于$f_{i,j}$如果移除了从第i-k个到第i-1个T共计k个T，那么状态转移可以表示为$f_{i,j} = \max \limits_{0\le k \le j} f_{i-k-1,j-k}\pm (\sum \limits_{c=i-k}^ia_c+k)$。这里注意$\pm$，当i-k-1为奇数时为加号。

对于状态的边界。前i个中删除i个不符合定义，但是将其设置为0可以便于编码，减少分类讨论情况，即$f_{i,i} = 0$；前i个中一个也不删除就是$a_{1}-a_{2}+a_{3}-\cdots a_{i}$，即$f_{i,0} = \sum \limits_{c=1}^i(-1)^{c+1}a_c$

同理可以求出$g_{i,j}$。

那么答案就是$max(f_{tsz, n}, -g_{tsz,n})$吗？

并不是，因为我们同一个T可以变化多次。对于相同的位置两次变化可以视为没有变化。所以$f_{tsz, n-2}, f_{tsz, n-4}, \cdots$，这些与n相差2的倍数的操作次数，也有可能是答案。

那么对$f_{tsz, n-1}, f_{tsz, n-3}, \cdots$，这些与n相差不是2的倍数的操作次数，又怎么说呢？

通过打表发现，$f_{tsz, n-1}$这种状态值有时候会比$f_{tsz,n}$大。

那么对于$f_{tsz, n-1}$再操作一步值会怎样变化？首先变大是不可能的，因为根据状态转移如果变大与$f_{tsz, n-1} > f_{tsz, n}$矛盾。所以只会变小。

变小会小多少呢？答案是1，因为操作一步无非是让移动变成了转向，会减少一步；或让转向变移动，这次移动根据上一条结论不会增加1步，而是减少一步。

所以答案为
$\max\limits_{i=1}^{2i \le n} (f_{tsz, n-2i}, -g_{tsz, n-2i}, f_{tsz, n-2i+1}, -g_{tsz, n-2i+1})$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    string s;
    int n;
    cin >> s;
    cin >> n;
    int sz = count(s.begin(), s.end(), 'T');
    if (n >= sz) {
        cout << s.size() - (n - sz) % 2 << "\n";
        return;
    }
    s.push_back('T');
    vector<int> a(2, 0);
    for (char i : s) {
        if (i == 'T')
            a.push_back(0);
        else
            a.back()++;
    }
    vector<int> p(a.size());
    for (int i = 1; i < p.size(); i++) {
        p[i] = p[i - 1] + a[i];
    }
    // for (auto i : p) {
    //     cout << i << " ";
    // }
    // cout << endl;
    int tsz = sz + 1;
    vector<vector<int>> f(a.size(), vector<int>(a.size()));
    for (int i = 1; i <= tsz; i++) {
        f[i][0] = f[i - 1][0];
        if (i % 2) {
            f[i][0] += p[i] - p[i - 1];
        } else {
            f[i][0] -= p[i] - p[i - 1];
        }
    }
    vector<vector<int>> g = f;
    for (int i = 1; i <= tsz; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k <= j; k++) {
                f[i][j] = max(f[i][j], f[i - 1 - k][j - k] + ((i - 1 - j) % 2 ? -1 : 1) * (p[i] - p[i - k - 1] + k));
                g[i][j] = min(g[i][j], g[i - 1 - k][j - k] + ((i - 1 - j) % 2 ? -1 : 1) * (p[i] - p[i - k - 1] + k));
            }
        }
    }
    // for (int i = 1; i <= tsz; i++) {
    //     for (int j = 0; j <= n; j++) {
    //         cout << i << " " << j << " " << f[i][j] << " " << g[i][j] <<
    //         "\n";
    //     }
    //     cout << "\n";
    // }
    // for (int i = 1; i <= tsz; i++) {
    //     cout << i << " " << n << " " << f[i][n] << " " << g[i][n] << "\n";
    // }
    // cout << s << "\n";
    int ans = 0;
    for (int i = n; i >= 0; i -= 2) {
        ans = max({ans, f[tsz][i], -g[tsz][i]});
    }
    for (int i = n - 1; i >= 0; i -= 2) {
        ans = max({ans, f[tsz][i] - 1, -g[tsz][i] + 1});
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}