一个长度为n的序列Yi, 将其分为不少于A且不多于B组, 求每组元素之和按位取或的最小值. - 子任务 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
上午出门之前看了一眼题, 一个上午过去了并没有什么思路.
下午回家之后又看了一眼题, 发现我把或看成了异或......
那么前4个子任务就好搞了. 从高位往低位依次贪心地确定答案. 设dp[i][j]表示分割i次, [0,j]是否存在结果的某些指定位等于0的方案. 如果第k位可以为0, 置答案的这一位为0, 并要求此后该位恒为0; 否则, 置答案的这一位为1, 不做要求.
从第40位向第0位枚举. 每次DP的时间复杂度O(n^3). 无法胜任子任务5. 试着用bitset优化, 每次DP O(n^3/w), 无济于事.
发现子任务5有特殊的限制 A=1. 但是我没啥好想法. 不知是得针对它设计不同的算法, 还是A的范围无关紧要, 逗你玩一玩......
看了题解, 对于A=1, 大的思路相同, 但是验证的时候DP换种状态. 设dp[i]表示[0,i]使结果的某些指定位等于0, 最少的分割次数. 只需验证dp[n-1]是否小于b.
再度观察子任务的分值, 发现有50%, A=1, 50%, A≥1.
收获 同一个问题, DP可以设计出不同的状态. 举例: - 0-1背包 (i, j) - 前i个物品, 体积为j, 最大价值; (i, j) - 前i个物品, 价值为j, 最小体积. - 最长上升子序列 (i, j) - 前i个元素, 最大值为j的上升子序列的最大长度; (i, j) - 前i个元素, 长度为j的上升子序列的末元素的最小值.
以上为状态和值之间的互换. 满足某一条件的最大/小结果 <-> 可满足结果的最小/大条件.
当值为0/1时, 状态中的一维可以变成值, 即最优化的目标. 是否存在满足某条件的结果 <-> 满足该条件的结果的最值.
const int N = 2000, inf = (1<<30)-1;
typedef long long ll;
int n, a, b;
ll S[N];
bool check(ll msk)
{
if (a > 1) {
static bitset<N> dp[N], s;
s.reset();
rep (i, 0, b) dp[i].reset();
dp[0][0] = !(S[0] & msk);
rep (i, 1, n) {
rep (j, 0, i)
s[j] = !((S[i]-S[j]) & msk);
rep (j, 1, b)
dp[j][i] = (dp[j-1] & s).any();
rep (j, 0, i+1)
dp[0][j] = !(S[j] & msk);
}
rep (i, a-1, b)
if (dp[i][n-1])
return true;
return false;
} else {
static int dp[N];
rep (i, 0, n) {
dp[i] = S[i] & msk ? inf : 0;
rep (j, 0, i)
if (!((S[i] - S[j]) & msk))
dp[i] = min(dp[i], dp[j] + 1);
}
return dp[n-1] < b;
}
}
int main()
{
scanf("%d%d%d", &n, &a, &b);
rep (i, 0, n)
scanf("%lld", S+i);
rep (i, 1, n)
S[i] += S[i-1];
ll ans = 0;
per (i, 40, 0) {
ll t = 1LL<<i;
if (!check(~ans & ~(t-1)))
ans |= t;
}
printf("%lld\n", ans);
return 0;
}