洛谷P17590题解

分析

题意

给一个由 . 和 X 组成的字符串，我们要选一个全是 X 的子序列，叫做好的子序列。

好的子序列有这么个特点：序列中间有一个分界点 $p$。

• 分界点前面：相邻两个元素的间隔是 $2x$；
• 分界点后面：相邻两个元素的间隔是 $x$。

$x$ 是某个正整数，$p$ 是序列里的某个位置，要求 $1\le p<k$（$k$ 是子序列长度）。

求能选出来的最长好子序列的长度。

思路

对于每一个是 X 的位置 $mid$，我们假设它就是分界点 $p$。再枚举每一个可能的步长 $x$。

• 向左拓展：从 $mid$ 出发，每次往前跳 $2x$，只要位置合法并且是 X 就继续，统计一共能取到多少个点，记为 $L$。$L$ 包含 $mid$ 自己。
• 向右拓展：从 $mid$ 出发，每次往前跳 $x$，只要位置合法并且是 X 就继续，统计一共能取到多少个点，记为 $R$。$R$ 包含 $mid$ 自己。

总长度为 $L + R - 1$。

所有 $mid$、所有 $x$ 全部跑一遍，记录最大的总长度就是答案。

边界：如果没有任何 X，$ans$ 保持初始 $0$，直接输出 0。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
char s[MAXN];
int n;
bool check(int idx) {
    if (idx < 1 || idx > n) return 0;
    return s[idx] == 'X';
}
int main() {
    cin >> n;
    scanf("%s", s + 1);
    int ans = 0;
    for (int mid = 1; mid <= n; mid++) {
        if (!check(mid)) continue;
        for (int x = 1; x <= n; x++) {
            int L = 1;
            int cur = mid;
            while (1) {
                int nxt = cur - 2 * x;
                if (nxt < 1 || !check(nxt)) break;
                L++;
                cur = nxt;
            }
            int R = 1;
            cur = mid;
            while (1) {
                int nxt = cur + x;
                if (nxt > n || !check(nxt)) break;
                R++;
                cur = nxt;
            }
            int tot = L + R - 1;
            if (tot > ans) ans = tot;
        }
    }
    cout << ans << endl;
    return 0;
}