当前位置：首页 > news >正文

[APIO2015]巴厘岛的雕塑

news 来源：原创 2024/5/2 5:38:49

刚开始看错题，以为是每一组或起来，求和的最小值，然后就瞎写了个dp，状态根本无法转移竟然过了六个点也是醉了

这个题根据数据可以分成两部分，可以按位贪心检验

对于n<=100的数据每一位直接n^3的dp就可以了

然后对于n>100的数据，A相当于没有限制，对每一位可以直接搞, g[i]代表到第i个雕塑至少分多少组才能符合要求

 1 #define MAXN 2010UL
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 
 9 int lg, n, B, A, f[110][110], g[MAXN];
10 ll ans, sum[MAXN];
11 
12 void Solve1() {
13     ll st = 0;
14     for(int l = lg ; l >= 0 ; -- l) {
15         memset(f, false, sizeof(f));
16         f[0][0] = true;
17         for(int k = 1 ; k <= B ; ++ k) {
18             for(int i = k ; i <= n ; ++ i) {
19                 for(int j = k-1 ; j < i ; ++ j) {
20                     if(f[k-1][j]&&(((sum[i]-sum[j])&(st|(1ll<<l)))==0)) {
21                         f[k][i] = true;
22                         break;
23                     }
24                 }
25             }
26         }
27         bool fg = false;
28         for(int i = A ; i <= B ; ++ i) if(f[i][n]) fg = true;
29         if(!fg) ans |= 1ll<<l;
30         else st |= 1ll<<l;
31     }
32     return;
33 }
34 
35 int MIN(int A, int B) { return A<B?A:B; }
36 
37 void Solve2() {
38     ll st = 0;
39     for(int l = lg ; l >= 0 ; -- l) {
40         memset(g, 0x3f, sizeof(g));
41         g[0] = 0;
42         for(int i = 1 ; i <= n ; ++ i) {
43             for(int j = 0 ; j < i ; ++ j) {
44                 if(((sum[i]-sum[j])&(st|(1ll<<l)))==0) g[i] = MIN(g[i], g[j]+1);
45             }
46         }
47         bool fg = (g[n]<=B);
48         if(!fg) ans |= 1ll<<l;
49         else st |= 1ll<<l;
50     }
51     return;
52 }
53 
54 int main() {
55     freopen("sculpture.in", "r", stdin);
56     freopen("sculpture.out", "w", stdout);
57     scanf("%d%d%d", &n, &A, &B);
58     for(int i = 1 ; i <= n ; ++ i) scanf("%lld", &sum[i]), sum[i] += sum[i-1];
59     lg = 0;
60     while((1ll<<lg)<=sum[n]) ++ lg;
61     if(A>1) Solve1();
62     else Solve2();
63     printf("%lld", ans);
64     return 0;
65 }