CF-Codeforces Round #483 (Div. 2)-D-XOR-pyramid

ACM模版

描述

题解

用 dp$dp$ 可解，用暴力预处理也可解。

如果用 dp$dp$ 解，我们需要用到两次记忆化，一次用来求解 l∼r$l\sim r$ 区间的答案，一次用来求解 l∼r$l\sim r$ 区间的所有子段中最大的解。第二个转移很好想，第一个转移是 dp[l][r] = fun_dp(l + 1, r) ^ fun_dp(l, r - 1)$\text{dp[l][r] = fun\_dp(l + 1, r) ^ fun\_dp(l, r - 1)}$。

如果用暴力预处理，可以根据杨辉三角找规律，暴力预处理的规律和杨辉三角的一样。

代码

#include <iostream>

using namespace std;

const int MAXN = 5555;

int n, q;
int a[MAXN];
int dp[MAXN][MAXN];
int dp_1[MAXN][MAXN];

int fun_dp(int l, int r)
{
    if (~dp[l][r])
    {
        return dp[l][r];
    }
    if (l == r)
    {
        return dp[l][r] = a[l];
    }
    return dp[l][r] = fun_dp(l + 1, r) ^ fun_dp(l, r - 1);
}

int fun_dp_1(int l, int r)
{
    if (~dp_1[l][r])
    {
        return dp_1[l][r];
    }
    if (l == r)
    {
        return dp_1[l][r] = dp[l][r];
    }
    return dp_1[l][r] = max(dp[l][r], max(fun_dp_1(l + 1, r), fun_dp_1(l, r - 1)));
}

int main(int argc, const char * argv[])
{
    memset(dp, -1, sizeof(dp));
    memset(dp_1, -1, sizeof(dp_1));

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", a + i);
    }

    cin >> q;
    int l, r;
    while (q--)
    {
        scanf("%d%d", &l, &r);
        fun_dp(l, r);
        fun_dp_1(l, r);
        printf("%d\n", dp_1[l][r]);
    }

    return 0;
}