BZOJ 4069 - [Apio2015]巴厘岛的雕塑

#dp #位运算
Published on 2016-05-04

题目地址

题目描述

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

分析

首先要知道，像状态 f[i][j] 将前 i 个分为 j 组得到的最小优美值 是不行的，原因是这里不是加法，而是按位或，动态规划的最优子结构贪心在这里不一定成立，所以这个 O(n3)O(n^3) 的暴力行不通。

有位运算？不妨考虑从高位向低位枚举，如果最高位可以是 00，那么就让它为 00，原因是如果最高为为 11 的话，后面的位即使全部是 0 也无法弥补，这是一个常用的枚举技巧。

枚举当前位 bit\mathrm{bit}，定义状态 f[i][j]f[i][j] 将前 ii 个分为 jj 组得到能否在满足前面位成立的情况下，使得当前位 bit\mathrm{bit} 为 00。

怎么才算满足前面位成立呢 ？假如上一位枚举的结果是可以为 00，那么这次转移的时候每组和的对应二进制位就只能为 00；假如上一位枚举的结果是为 11，那么每组和的对应二进制位就是随意。这里采用按位或来巧妙判断，参见代码。

则当前 bit\mathrm{bit} 位可为 0 当且仅当 f[n][i]=1,i∈[A,B]f[n][i] = 1, i \in [A, B]。

这一算法的复杂度是: O(n3logS)O(n^3\log S)。不足以通过最后一个子任务。

由于最后一个子任务的 A=1A = 1，考虑精简状态。g[i]g[i] 使得前 ii 位在满足前面位成立的情况下，使得当前位 bit\mathrm{bit} 为 00 至少要分多少组。则当前 bit\mathrm{bit} 位可为 0 当且仅当 g[i]≤Bg[i] \le B。

复杂度 O(n2logS)O(n^2\log S)。

代码

//  Created by Sengxian on 5/3/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4069 DP + 位运算
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

typedef long long ll;
const int maxn = 2000 + 3;
int n, A, B, g[maxn];
bool f[maxn][maxn];
ll s[maxn];

inline bool check(ll sum, int bit, ll ans) { //ans 为 1 的部分，sum 为 0 也是合法的，这里采用按位或来巧妙判断
    return ((sum >> (bit + 1)) | ans) == ans && ((sum >> bit) & 1) == 0;
}

ll solve2() {
    ll ans = 0;
    for (int bit = (int)log2(s[n]); bit >= 0; --bit) {
        g[0] = 0;
        for (int i = 1; i <= n; ++i) {
            g[i] = B + 1;
            for (int k = 1; k <= i; ++k)
                if (g[k - 1] + 1 < g[i] && check(s[i] - s[k - 1], bit, ans)) //g[k - 1] + 1 < g[i] 这个剪枝直接快了4s
                    g[i] = min(g[i], g[k - 1] + 1);
        }
        ans = ans << 1 | (g[n] > B);
    }
    return ans;
}

ll solve1() {
    ll ans = 0;
    for (int bit = (int)log2(s[n]); bit >= 0; --bit) {
        memset(f[0], 0, sizeof f[0]);
        f[0][0] = true;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= min(i, B); ++j) {
                f[i][j] = false;
                for (int k = 1; k <= i && !f[i][j]; ++k)
                    f[i][j] |= f[k - 1][j - 1] && check(s[i] - s[k - 1], bit, ans);
            }
        bool flag = false;
        for (int i = A; i <= B && !flag; ++i) flag |= f[n][i];
        ans = ans << 1 | !flag;
    }
    return ans;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
    #endif
    n = ReadInt(), A = ReadInt(), B = ReadInt();
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + ReadInt();
    printf("%lld\n", A > 1 ? solve1() : solve2());
    return 0;
}
BZOJ 4197 - [Noi2015]寿司晚宴