题目地址：洛谷：【P3646】[APIO2015]巴厘岛的雕塑 – 洛谷、BZOJ：Problem 4069. — [Apio2015]巴厘岛的雕塑

题目描述

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
在这条主干道上一共有 N 座雕塑，为方便起见，我们把这些雕塑从 1 到 N 连续地进行标号，其中第 i 座雕塑的年龄是 Yi 年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。
下面是将雕塑分组的规则：
这些雕塑必须被分为恰好 X 组，其中 A< = X< = B，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。
计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。
请问政府能得到的最小的最终优美度是多少？

输入输出格式

输入格式：
输入的第一行包含三个用空格分开的整数 N,A,B。
第二行包含 N 个用空格分开的整数 Y1,Y2,…,YN。

输出格式：
输出一行一个数，表示最小的最终优美度。

输入输出样例

输入样例#1：

6 1 3
8 1 2 1 5 4

输出样例#1：

11

说明

子任务 1 （9 分），1< = N< = 20，1< = A< = B< = N，0< = Yi< = 1000000000
子任务 2 （16 分），1< = N< = 50，1< = A< = B< = min{20,N}，0< = Yi< = 10
子任务 3 （21 分），1< = N< = 100，A=1，1< = B< = N，0< = Yi< = 20
子任务 4 （25 分），1< = N< = 100，1< = A< = B< = N，0< = Yi< = 1000000000
子任务 5 （29 分），1< = N< = 2000，A=1，1< = B< = N，0< = Yi< = 1000000000

题解

首先既然是最小，又涉及位运算，应该是对二进制位进行DP没跑了。我们从高位往低位来做DP。
其实要解决的问题是“这一位上能不能填0”，那么我们设计DP状态dp[i][j]表示前i个划分成j段，这一位之前的高位与目前最优解相同，这一位能不能填0。枚举k，从dp[k][j – 1]这个状态来进行转移，如果j~i这一段的和能确保目前最优解（即((sum >> pos) | ans) == ans）且这种情况下当前位能填0（即!(sum & (1ll << (pos - 1)))），那么可以转移。
每一位的DP结束后，我们从dp[n][A]到dp[n][B]找是否有DP状态表示解可行，有的话这一位就可以为0，否则必须为1。
那么我们可以知道这个的复杂度是O(n^3 \log (\sum y_i))的，对于子任务5的n范围有些吃紧。
接下来，为了能过子任务5，我们得有一点面向子任务编程的想法。子任务5的特点是A=1，也就是说上面所说的下界限制是没有了的。那么我们考虑直接降低DP状态维度来优化复杂度。我们让dp[i]表示前i个符合目前最优解且最后一位能填0最少的划分段数。我们可以枚举k，从dp[k]像上面类似地往后转移，最后判断的依据是dp[n]是否超过B，超过这一位就必须得为1了。因为不需要枚举j了，复杂度降为O(n^2 \log (\sum y_i))。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 2005;

int n, a, b;
LL y[MAXN];
int f[MAXN][MAXN], g[MAXN];

int main() {
    n = readint();
    a = readint();
    b = readint();
    for(int i = 1; i <= n; i++) {
        y[i] = y[i - 1] + readint();
    }
    int len = 0;
    LL t = y[n];
    while(t) {
        len++;
        t >>= 1;
    }
    LL ans = 0;
    if(a == 1) {
        for(int pos = len; pos; pos--) {
            memset(g, 0x3f, sizeof(g));
            g[0] = 0;
            for(int i = 1; i <= n; i++) {
                for(int j = 0; j < i; j++) {
                    if(g[j] < b) {
                        LL sum = y[i] - y[j];
                        if(((sum >> pos) | ans) == ans && !(sum & (1ll << (pos - 1)))) {
                            g[i] = std::min(g[i], g[j] + 1);
                        }
                    }
                }
            }
            ans <<= 1;
            if(g[n] > b) ans++;
        }
    } else {
        for(int pos = len; pos; pos--) {
            memset(f, 0, sizeof(f));
            f[0][0] = 1;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= i; j++) {
                    for(int k = 0; k < i; k++) {
                        if(f[k][j - 1]) {
                            LL sum = y[i] - y[k];
                            if(((sum >> pos) | ans) == ans && !(sum & (1ll << (pos - 1)))) {
                                f[i][j] = 1;
                            }
                        }
                    }
                }
            }
            ans <<= 1;
            bool success = false;
            for(int i = a; i <= b; i++) {
                if(f[n][i]) {
                    success = true;
                    break;
                }
            }
            if(!success) ans++;
        }
    }
    printf("%lld", ans);
    return 0;
}