【大意】
给定(A)，(B)，使一个区间的元素分为(Ale xle B)组，每组的贡献为组内元素之和，最小化所有组贡献的或运算和。
【分析】
开始一晃眼没看见区间连续这个条件，感觉做了假的题。。。
思考一个容易想到的(dp)式子，设(f[i][j])表示前(i)个元素，分为(j)个组的最小化答案，考虑枚举转移点(k)，然后转移。。。。
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll INF = 5e18;
const int MAX = 2000 + 5;
inline ll read() {
ll res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}
ll n, A, B, Y[MAX], sum[MAX], f[MAX][MAX], ans = INF;
int main() {
n = read(), A = read(), B = read();
for (int i = 1;i <= n; ++i)
for (int j = 0;j <= n; ++j) f[i][j] = INF;
for (int i = 1;i <= n; ++i) Y[i] = read(), sum[i] = sum[i - 1] + Y[i], f[i][1] = sum[i];
for (int i = 1;i <= n; ++i) {
int limit = min((ll)i, B);
for (int j = 2;j <= limit; ++j) {
for (int k = 1;k < i; ++k) {
f[i][j] = min(f[i][j], f[k][j - 1] | (sum[i] - sum[k]));
}
}
}
for (int i = A;i <= B; ++i) ans = min(ans, f[n][i]);
printf("%lld", ans);
return 0;
}
去提交。。啊！(75Pt)？？？(TLE)我还可以接受，还有的点(WA)？
仔细思考了一下，发现这个式子并不满足无后效性。为什么？你选择前面的使它最小化了，但在或运算下，后面的影响你是不知道的。换句话说，本题中，若按之前的(dp)方程转移，局部最优解并不是全局最优解。
我们需要重新思考。
由或这个二进制运算和题目明显的提示，想到拆分考虑二进制数位，又因为最小化，所以贪心地从最高位开始对每一位进行考虑。
对于每一位(pos)，我们用(f[i][j])表示用前(i)个元素，分成(j)组，能否使当前位为(0)（因为要最小化嘛）。
枚举转移点(k)，若(f[k][j-1])为真，且(sum[k+1...i])在当前(pos)位上是(0)，那么就可以转移过来(f[i][j]=1)。然后累计(ans)。
若存在(f[n][i]=1(Ale ile B))那么该位就可以等于(0)。
再仔细思考，我们会发现若直接这样做，有可能会存在着低位的分组与高位的分组发生冲突。显然，我们应保留高位分组的情况，所以说，我们应保留之前已匹配好的位的状态，并且让转移也不能与这个状态发生冲突。
接着来思考子任务(5)。
我们会发现它的数据有特殊性：(A=1)。
怎么特殊？分组没有下限！
那我直接记录最少能用多少组让(pos)位可以填(0)不就行了？
设(g[i])表示前(i)位最少能分成多少组使当前位(pos)可以填(0)，那么同样的，只要满足转移条件，就有(g[i]=min(g[i],g[k] + 1))。其中除(g[0]=0)以外，其余(g)均为(INF)。
然后就写了个分段(dp)。
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define ll long long
#define Re register
using namespace std;
const int MAX = 2000 + 5;
inline ll read() {
ll res = 0; bool f = 0; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = 1; ch = getchar(); }
while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
return f ? (~ res + 1) : res;
}
ll Y[MAX], sum[MAX], f[MAX][MAX], ans;
int n, A, B, g[MAX];
bool flag;
inline void solution_1() {
int limit = log2(sum[n]) + 1;
for (int pos = limit; pos >= 0; --pos) {
ll res = ans | ((1LL << pos) - 1LL);
memset(g, 127, sizeof g);
g[0] = 0;
for (int i = 1;i <= n; ++i) {
for (int k = 0;k < i; ++k) {
if (((sum[i] - sum[k]) | res) == res) {
g[i] = min(g[i], g[k] + 1);
}
}
}
if (g[n] > B) ans |= (1LL << pos);
}
}
inline void solution_2() {
int limit = log2(sum[n]) + 1;
for (int pos = limit;pos >= 0; --pos) {
ll res = ans | ((1LL << pos) - 1LL);
memset(f, 0, sizeof f);
f[0][0] = 1;
flag = 0;
for (int i = 1;i <= n; ++i) {
int up = min(i, (int)B);
for (int j = 1;j <= up; ++j) {
for (int k = j - 1;k < i; ++k) {
if (f[k][j - 1] && ((sum[i] - sum[k]) | res) == res) {
f[i][j] = 1;
}
}
}
}
for (int i = A;i <= B; ++i) if (f[n][i]) flag = 1;
if (!flag) ans |= (1LL << pos);
}
}
int main() {
n = read(), A = read(), B = read();
for (int i = 1;i <= n; ++i) Y[i] = read(), sum[i] = sum[i - 1] + Y[i];
if (A == 1) solution_1();
else solution_2();
printf("%lld", ans);
return 0;
}