首页 > 代码库 > 繁华模拟赛 ljw分雕塑
繁华模拟赛 ljw分雕塑
/*用f[i][k]表示考虑到第i个雕塑,分成k组,可不可行(这是一个bool类型的数组)转移:f[i][k]=f[j][k-1],sum[i]-sum[j]合法*/#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>using namespace std;typedef long long ll;const int max_n = 2010;const ll inf = 1e15;inline int getnum() { int ans = 0; char c; bool flag = false; while (!isdigit(c = getchar()) && c != ‘-‘); if (c == ‘-‘) flag = true; else ans = c - ‘0‘; while (isdigit(c = getchar())) ans = ans * 10 + c - ‘0‘; return ans * (flag ? -1 : 1);} int a[max_n], limit_A, limit_B, n;;namespace part1 { const int max_n_small = 110; bool able[max_n_small][max_n_small]; inline bool check(ll ba, ll tar) { memset(able, 0, sizeof(able)); able[0][0] = true; for (int i = 1; i <= n; i++) for (int j = 1; j <= limit_B; j++) { ll sum = a[i]; for (int k = i - 1; k >= 0; k--) { if (able[k][j - 1] && (sum | ba) < tar) { able[i][j] = true; break; } sum += a[k]; } } for (int i = limit_A; i <= limit_B; i++) if (able[n][i]) return true; return false; } inline void solve() { ll sum = 0; for (int i = 1; i <= n; i ++) sum += a[i]; sum <<= 1; int max_bit = 0; for (; sum >> max_bit; max_bit++); max_bit--; ll ans = 0; for (int i = max_bit; i >= 0; i--) { ll tar = ans | (1LL << i); if (!check(ans, tar)) ans += (1LL << i); } cout << ans << endl; }}namespace part2 { const int max_n_small = 2010; bool able[max_n_small]; int f[max_n_small]; inline bool check(ll ba, ll tar) { memset(able, 0, sizeof(able)); memset(f, 0x7f, sizeof(f)); able[0] = true; f[0] = 0; for (int i = 1; i <= n; i++) { ll sum = a[i]; for (int k = i - 1; k >= 0; k--) { if (able[k] && (sum | ba) < tar) { able[i] = true; f[i] = min(f[i], f[k] + 1); } sum += a[k]; } } if (able[n] && f[n] <= limit_B) return true; else return false; } inline void solve() { ll sum = 0; for (int i = 1; i <= n; i ++) sum += a[i]; sum <<= 1; int max_bit = 0; for (; sum >> max_bit; max_bit++); max_bit--; ll ans = 0; for (int i = max_bit; i >= 0; i--) { ll tar = ans | (1LL << i); if (!check(ans, tar)) ans += (1LL << i); } cout << ans << endl; }}int main() { freopen("sculpture.in", "r", stdin); freopen("sculpture.out", "w", stdout); n = getnum(); limit_A = getnum(); limit_B = getnum(); for (int i = 1; i <= n; i++) a[i] = getnum(); if (n > 100) part2::solve(); else part1::solve();}
繁华模拟赛 ljw分雕塑
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。