首页 > 代码库 > 繁华模拟赛 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分雕塑