BZOJ4069【APIO2015】巴厘岛的雕塑 < DP >

Problem

【APIO2015】巴厘岛的雕塑

$\mathrm{Time\;Limit: \;10\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

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

Input

输入的第一行包含三个用空格分开的整数$N,A,B$。
第二行包含$N$个用空格分开的整数$Y_1,Y_2,\cdots,Y_N$。

Output

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

Sample Input

6 1 3
8 1 2 1 5 4

Sample Output

11

Explanation

将这些雕塑分为$2$组，$(8,1,2)$和$(1,5,4)$，它们的和是$(11)$和$(10)$，最终优美度是$(11\mid10)=11$。不难验证，这也是最终优美度的最小值。

HINT

子任务编号	$N$	$A,B$	$Y_i$	分值
$1$	$1\le N\le20$	$A,B\le N$	$0\le Y_i\le10^9$	$\mathrm{9\;pts}$
$2$	$1\le N\le 50$	$A,B\le\min(20,N)$	$0\le Y_i\le10$	$\mathrm{16\;pts}$
$3$	$1\le N\le100$	$A=1,\;B\le N$	$0\le Y_i\le20$	$\mathrm{21\;pts}$
$4$	$1\le N\le100$	$A,B\le N$	$0\le Y_i\le10^9$	$\mathrm{25\;pts}$
$5$	$1\le N\le2000$	$A=1,\;B\le N$	$0\le Y_i\le10^9$	$\mathrm{29\;pts}$

标签：DP

Solution

奇葩的面向数据编程题。

由于算答案是按位或，可以考虑从高位向低位贪心，每次判断在前面的位都取到最优情况下，这一位能否取$0$。这个判断的过程可以$\mathrm{DP}$实现。
$f[i][j]$表示考虑前$i$个雕塑，分成$j$个组，能否在当前位上取$0$。
那么$f[i][j]=true$当且仅当$\exists k\in[j-1,i)$，满足$f[k][j-1]=true$，并且$sum_{k+1,i}$和当前答案取或的结果还是当前答案（即不会使得前面位上不为最优解），还需要$sum_{k+1,j}$在当前位上的值为$0$（这样当前位才能取$0$）。
求出所有$f$后，判断是否$\exists t\in[A,B]$满足$f[n][t]=true$，如果存在则可以取$0$，否则此位取$1$。

然而这样并不能得满分。上面的方法是$O(n^3)$处理出所有$f$值，不能通过$n=2000$的$\mathrm{Subtask\;5}$。

而对于$\mathrm{Subtask\;5}$，发现$A=1$，则每次使得分的组数量尽量小肯定是最优的。于是用$g[i]$表示当前位考虑前$i$个雕塑，最少需要分成几组才能使当前位上可以取$0$。如果在当前位处理$g$后发现$g[n]>B$，那么必须取$1$，否则可以取$0$。这样复杂度降成了$O(n^2)$，可以解决$\mathrm{Subtask\;5}$。

综上，特判数据分两种情况分别做即可。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, A, B; lnt s[MAX_N+5], ans;
bool f[MAX_N+5][MAX_N+5]; int g[MAX_N+5];
void sub1() {
    for (int p = m, flag = 1; p; p--, flag = 1) {
        memset(f, false, sizeof f), f[0][0] = true;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++)
            for (int k = j-1; k < i; k++) if (f[k][j-1]) {
                if ((((s[i]-s[k])>>p)|ans)^ans) continue;
                if ((s[i]-s[k])&(1LL<<(p-1))) continue;
                f[i][j] = true; break;
            }
        for (int i = A; i <= B; i++)
            if (f[n][i]) {flag = 0; break;}
        (ans <<= 1) |= flag;
    }
    printf("%lld\n", ans);
}
void sub2() {
    for (int p = m; p; p--) {
        memset(g, 0x3f, sizeof g), g[0] = 0;
        for (int i = 1; i <= n; i++) for (int k = 0; k < i; k++) {
            if ((((s[i]-s[k])>>p)|ans)^ans) continue;
            if ((s[i]-s[k])&(1LL<<(p-1))) continue;
            g[i] = min(g[i], g[k]+1);
        }
        (ans <<= 1) |= (g[n] > B);
    }
    printf("%lld\n", ans);
}
int main() {
    read(n), read(A), read(B);
    for (int i = 1; i <= n; i++)
        read(s[i]), s[i] += s[i-1];
    for (lnt i = s[n]; i; i >>= 1) m++;
    return (A != 1 ? sub1() : sub2()), 0;
}