2017多校六 1008题 hdu 6103 Kirinriki 尺取法

题目链接


题意:

给定一个串 s,要找其两个子串 A, B, 使得在满足 cost = m 的前提下,子串长度取到最大值。

cost 的定义为 sigma(i = 0 ~ n - 1) (abs(A[i] - B[n - 1 - i])).


思路:

枚举中心点向两边扩展。

对于每一个确定的中心点(左边子串的右端点,右边子串的左端点),运用尺取法判断 cost = m 的前提下子串能取到的最大长度,这就是一个很常规的尺取的题目了:固定一个端点移动另一个直到不满足条件,求一个值,再将固定的端点移动一格,然后继续移动另一个端点直到不满足条件,这样周而复始...

又因为考虑到最终答案的两个子串之间可能相隔奇数个位置,也可能相隔偶数个位置,因此枚举时就要枚举两种情况。


Code:

#include bits/stdc++.h
#define maxn 5010
char s[maxn];
int n;
inline int max(int a, int b) { return a  b ? a : b; }
int count1(char* s) {
    int len = strlen(s), ret = 0;
    for (int i = 0; i  len - 1; ++i) {
        int l1, r1, l2, r2, sum = 0, ans = 0;
        l1 = r1 = i, l2 = r2 = i + 1;
        while (true) {
            bool flag = false;
            while (l1 = 0  r2  len) {
                sum += abs(s[l1] - s[r2]);
                if (sum  n) break;
                --l1, ++r2;
            }
            ans = max(ans, r1 - l1);
            if (sum = n) break;
            sum -= abs(s[r1--] - s[l2++]);
            --l1, ++r2;
        }
        ret = max(ret, ans);
    }
    return ret;
}
int count2(char* s) {
    int len = strlen(s), ret = 0;
    for (int i = 1; i  len - 1; ++i) {
        int l1, r1, l2, r2, sum = 0, ans = 0;
        l1 = r1 = i - 1, l2 = r2 = i + 1;
        while (true) {
            bool flag = false;
            while (l1 = 0  r2  len) {
                sum += abs(s[l1] - s[r2]);
                if (sum  n) break;
                --l1, ++r2;
            }
            ans = max(ans, r1 - l1);
            if (sum = n) break;
            sum -= abs(s[r1--] - s[l2++]);
            --l1, ++r2;
        }
        ret = max(ret, ans);
    }
    return ret;
}
void work() {
    scanf("%d%s", n, s);
    printf("%d\n", max(count1(s), count2(s)));
}
int main() {
    int T;
    scanf("%d", T);
    while (T--) work();
    return 0;
}


就是这个尺取法写起来有点绕Orz.调了大半天...脑子太糊涂...还是太弱了

最新回复(0)
/jishuqitQF0Zswyqy9UTEC0FqOGsPoegglVBnyt90pA_3D_3D4794987
8 简首页