繁华模拟赛 ljw分雕塑

繁华模拟赛 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 = ;
const ll inf = 1e15; inline int getnum() {
int ans = ; char c; bool flag = false;
while (!isdigit(c = getchar()) && c != '-');
if (c == '-') flag = true; else ans = c - '';
while (isdigit(c = getchar())) ans = ans * + c - '';
return ans * (flag ? - : );
} int a[max_n], limit_A, limit_B, n;; namespace part1 {
const int max_n_small = ;
bool able[max_n_small][max_n_small]; inline bool check(ll ba, ll tar) {
memset(able, , sizeof(able));
able[][] = true; for (int i = ; i <= n; i++)
for (int j = ; j <= limit_B; j++) {
ll sum = a[i];
for (int k = i - ; k >= ; k--) {
if (able[k][j - ] && (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 = ;
for (int i = ; i <= n; i ++)
sum += a[i];
sum <<= ;
int max_bit = ;
for (; sum >> max_bit; max_bit++);
max_bit--; ll ans = ;
for (int i = max_bit; i >= ; i--) {
ll tar = ans | (1LL << i);
if (!check(ans, tar))
ans += (1LL << i);
}
cout << ans << endl;
}
} namespace part2 {
const int max_n_small = ;
bool able[max_n_small];
int f[max_n_small]; inline bool check(ll ba, ll tar) {
memset(able, , sizeof(able));
memset(f, 0x7f, sizeof(f));
able[] = true;
f[] = ; for (int i = ; i <= n; i++) {
ll sum = a[i];
for (int k = i - ; k >= ; k--) {
if (able[k] && (sum | ba) < tar) {
able[i] = true;
f[i] = min(f[i], f[k] + );
} sum += a[k];
}
} if (able[n] && f[n] <= limit_B)
return true;
else
return false;
} inline void solve() {
ll sum = ;
for (int i = ; i <= n; i ++)
sum += a[i];
sum <<= ;
int max_bit = ;
for (; sum >> max_bit; max_bit++);
max_bit--; ll ans = ;
for (int i = max_bit; i >= ; 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 = ; i <= n; i++) a[i] = getnum(); if (n > )
part2::solve();
else
part1::solve();
}
上一篇:脚本控制向Android模拟拨打电话,发送短信,定位设置功能


下一篇:Java字符串处理