【UOJ|【UOJ #110】【APIO 2015】Bali Sculptures 【UOJ#110】【APIO2015】BaliSculpt

【【UOJ|【UOJ #110】【APIO 2015】Bali Sculptures】http://uoj.ac/problem/110
这道题subtask4和subtask5是不同的算法。
主要思想都是从高位到低位贪心确定答案。
对于subtask4，n比较小，设\(f(i,j)\)表示前\(i\)个雕塑分成\(j\)组能否满足当前答案，最后检查\(f(n,A\sim B)\)是否有值为true的，时间复杂度\(O(n^3\log\sum Y_i)\)。
对于subtask5，n比较大，但A=1，设\(f(i)\)表示前\(i\)个雕塑要满足当前答案最少能分成多少组，最后检查\(f(n)\)是否不大于B，时间复杂度\(O(n^2\log\sum Y_i)\)。

#include #include #include using namespace std; typedef long long ll; const int N = 2003; int n, A, B, Y[N]; ll sum[N], num = (1ll << 41) - 1; namespace lalala { bool f[N][N]; bool can(ll x) { f[0][0] = true; for (int i = 1; i <= n; ++i) for (int j = 1; j <= B && j <= i; ++j) { f[i][j] = false; for (int k = i - 1; k >= 0; --k) if (((sum[i] - sum[k]) | x) <= x && f[k][j - 1]) { f[i][j] = true; break; } } for (int i = A; i <= B; ++i) if (f[n][i]) return true; return false; }void solve() { for (int i = 40; i >= 0; --i) if (can(num ^ (1ll << i))) num ^= (1ll << i); printf("%lld\n", num); } }namespace hahaha { int f[N]; bool can(ll x) { for (int i = 1; i <= n; ++i) { f[i] = B + 1; for (int j = i - 1; j >= 0; --j) if (((sum[i] - sum[j]) | x) <= x && f[j] + 1 < f[i]) f[i] = f[j] + 1; } return f[n] <= B; }void solve() { for (int i = 40; i >= 0; --i) if (can(num ^ (1ll << i))) num ^= (1ll << i); printf("%lld\n", num); } }int main() { scanf("%d%d%d", &n, &A, &B); for (int i = 1; i <= n; ++i) scanf("%d", Y + i), sum[i] = sum[i - 1] + Y[i]; if (A == 1) hahaha::solve(); else lalala::solve(); return 0; }

转载于:https://www.cnblogs.com/abclzr/p/6728841.html