luogu3646 巴厘岛的雕塑 (dp)

我们一位一位地来做，每次判断这一位能否放0，而且要在满足前几位的情况下。用dp来判断

具体来说，设f[i][j]表示前i个划分成j个区间能否满足，那么我们会有转移trans[i][k+1]，当区间[i,k]的和在某些位上不是1时trans[i][k+1]=1

这些位，就是正在做的这位和它之前确定下来的取0的位数

那么每次就看f[N+1][A...B]是否有值，就可以确定下来这位答案到底是放0还是1了

这样做的复杂度，是O(n^3logV)的，最后一个子任务过不去

发现最后一个子任务A=1，那我们就可以在dp时少记一维，令f[i]表示使前i个数满足的最小区间数，看最后f{N+1]能否<=B就可以了

（或者像我一样zz地写一个最短路）

有一个要注意的点，就是<<操作，如果超出范围，是要写成类似于1LL<<55这样的

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define ll long long
 4 using namespace std;
 5 const int maxm=110,maxn=2020;
 6 
 7 inline ll rd(){
 8     ll x=0;char c=getchar();int neg=1;
 9     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
10     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
11     return x*neg;
12 }
13 
14 int N,M,A,B,dis[maxn];
15 bool tmp[maxn][maxn];
16 bool trans[maxn][maxn],f[maxn][maxn],flag[maxn];
17 ll sum[maxn],num[maxn];
18 priority_queue<pa,vector<pa>,greater<pa> > q;
19 
20 inline bool dp(){
21     memset(f,0,sizeof(f));f[0][1]=1;
22     for(int i=0;i<B;i++){
23         for(int j=1;j<=N;j++){if(!f[i][j]) continue;
24             for(int k=j+1;k<=N+1;k++){
25                 if(!trans[j][k]) continue;
26                 f[i+1][k]=1;
27             }
28         }
29     }bool can=0;
30     for(int i=A;i<=B;i++){
31         can|=f[i][N+1];
32     }return can;
33 }
34 inline bool dijkstra(){
35     memset(dis,127,sizeof(dis));while(!q.empty()) q.pop();
36     memset(flag,0,sizeof(flag));
37     dis[1]=0;q.push(make_pair(0,1));
38     while(!q.empty()){
39         int p=q.top().second;q.pop();if(flag[p]) continue;
40         if(p==N+1) break;
41         for(int i=p+1;i<=N+1;i++){
42             if(!trans[p][i]||dis[i]<=dis[p]+1) continue;
43             dis[i]=dis[p]+1;q.push(make_pair(dis[i],i));
44         }
45     }return dis[N+1]<=B;
46 }
47 
48 inline void solve(){
49     ll ans=0;int i,j,k;
50     for(i=1;i<=N;i++) sum[i]=sum[i-1]+num[i];
51     ll l=sum[N];while(l) M++,l>>=1;
52     memset(trans,1,sizeof(trans));
53     for(int t=M;t;t--){
54         memcpy(tmp,trans,sizeof(tmp));
55         for(int i=1;i<=N;i++){
56             for(int j=i;j<=N;j++){
57                 if((sum[j]-sum[i-1])&(1LL<<(t-1))) trans[i][j+1]=0;
58             }
59         }
60         bool can=(A==1)?dijkstra():dp();
61         if(!can){
62             ans|=1LL<<(t-1);memcpy(trans,tmp,sizeof(tmp));
63         }
64     }
65     printf("%lld\n",ans);
66 }
67 
68 int main(){
69     int i,j,k;
70     //freopen("1967.in","r",stdin);
71     N=rd(),A=rd(),B=rd();
72     for(i=1;i<=N;i++) num[i]=rd();
73     solve();
74     return 0;
75 }

来源：https://www.cnblogs.com/Ressed/p/9643698.html