[APIO2015]巴厘岛的雕塑 --- 贪心 + 枚举

时间：2021-02-24 19:40:02

[APIO2015]巴厘岛的雕塑 

题目描述

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。

在这条主干道上一共有\(N\)座雕塑，为方便起见，我们把这些雕塑从 1 到\(N\)连续地进行标号，其中第\(i\)座雕塑的年龄是\(Y_{i}\)年。

为了使这条路的环境更加优美，*想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。

下面是将雕塑分组的规则：

这些雕塑必须被分为恰好\(X\)组，其中 \(A<=X<=B\)，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。

同一组中的所有雕塑必须位于这条路的连续一段上。

当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。

计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。

请问*能得到的最小的最终优美度是多少?

数据范围：

[APIO2015]巴厘岛的雕塑 --- 贪心 + 枚举

或值最大 ---)  按位贪心即可

为了保证最小，从高位向低位贪心（虽然最大是一样的。。。）

那么怎么确定最小的答案呢？

注意到，高位贪心的结果需要被保留（高位一定更优）。

因此，维护\(dp(i,j)\)表示枚举到第\(i\)位，分成了\(j\)块，能否在满足高位贪心的同时可不可以让当前位为0。

如果\(dp(n,A)...dp(n,B)\)中有一个满足，那么当前位可以为0，计入高位。

如何转移？

枚举即可，枚举所有的区间来转移，确定一位能否为0需要\(n^{2}*B\)时间

总共需要时间\(O(\log n *B*n^{2})\)

可以发现过不掉最后一个点。

但是\(A=1\)非常的显眼，有什么用？

这告诉我们没有下届，只有上届。

因此，只要求出至少需要多少块才能在满足高位贪心的同时让当前位为0，同样可以判断。

复杂度可以降至：

\(O(\log n * n ^{2})\)

#include <cstdio>

#include <cstring>

#define ll long long

#define ri register int

using namespace std;

char RR[], *S = RR, *T = RR + ;

inline char gc() {

    if(S == T) fread(RR, , , stdin), S = RR;

    return *S ++;

}

inline int read() {

    int p = , w = ; char c = gc();

    while(c > '' || c < '') {

        if(c == '-') w = -;

        c = gc();

    }

    while(c >= '' && c <= '') {

        p = p *  + c - '';

        c = gc();

    }

    return p;

}

template <typename re>

inline void upmin(re &a, re b) { if(a > b) a = b; }

int n, A, B;

ll ans, sum[], bit[];

bool dp[][];

int f[];

void Solve1() {

    for(ri p = ; p; p --) {

        memset(dp, , sizeof(dp));

        dp[][] = ;

        for(ri i = ; i <= n; i ++)

        for(ri j = ; j <= i; j ++)

        for(ri k = j - ; k <= i - ; k ++)

        if(dp[k][j - ]) {

            ll pp = sum[i] - sum[k];

            if(((pp >> p) | ans) == ans)

            if((pp & bit[p - ]) == ) dp[i][j] = ;

        }

        ans <<= ; ans |= ;

        for(ri i = A; i <= B; i ++)

        if(dp[n][i]) { ans ^= ; break; }

    }

    printf("%lld\n", ans);

}

void Solve2() {

    for(ri p = ; p; p --) {

        for(ri i = ; i <= n; i ++) f[i] = ;

        for(ri i = ; i <= n; i ++)

        for(ri j = ; j <= i - ; j ++) {

            ll pp = sum[i] - sum[j];

            if(((pp >> p) | ans) == ans)

            if((pp & bit[p - ]) == ) upmin(f[i], f[j] + );

        }

        ans <<= ;

        if(f[n] > B) ans |= ;

    }

    printf("%lld\n", ans);

}

int main() {

    for(ri i = ; i <= ; i ++) bit[i] = 1LL << i;

    n = read(); A = read(); B = read();

    for(ri i = ; i <= n; i ++) sum[i] = sum[i - ] + read();

    if(A == ) Solve2();

    else Solve1();

    return ;

}

Aha!

相关文章