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这样的

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define ll long long

 using namespace std;

 const int maxm=,maxn=;

 inline ll rd(){

     ll x=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 int N,M,A,B,dis[maxn];

 bool tmp[maxn][maxn];

 bool trans[maxn][maxn],f[maxn][maxn],flag[maxn];

 ll sum[maxn],num[maxn];

 priority_queue<pa,vector<pa>,greater<pa> > q;

 inline bool dp(){

     memset(f,,sizeof(f));f[][]=;

     for(int i=;i<B;i++){

         for(int j=;j<=N;j++){if(!f[i][j]) continue;

             for(int k=j+;k<=N+;k++){

                 if(!trans[j][k]) continue;

                 f[i+][k]=;

             }

         }

     }bool can=;

     for(int i=A;i<=B;i++){

         can|=f[i][N+];

     }return can;

 }

 inline bool dijkstra(){

     memset(dis,,sizeof(dis));while(!q.empty()) q.pop();

     memset(flag,,sizeof(flag));

     dis[]=;q.push(make_pair(,));

     while(!q.empty()){

         int p=q.top().second;q.pop();if(flag[p]) continue;

         if(p==N+) break;

         for(int i=p+;i<=N+;i++){

             if(!trans[p][i]||dis[i]<=dis[p]+) continue;

             dis[i]=dis[p]+;q.push(make_pair(dis[i],i));

         }

     }return dis[N+]<=B;

 }

 inline void solve(){

     ll ans=;int i,j,k;

     for(i=;i<=N;i++) sum[i]=sum[i-]+num[i];

     ll l=sum[N];while(l) M++,l>>=;

     memset(trans,,sizeof(trans));

     for(int t=M;t;t--){

         memcpy(tmp,trans,sizeof(tmp));

         for(int i=;i<=N;i++){

             for(int j=i;j<=N;j++){

                 if((sum[j]-sum[i-])&(1LL<<(t-))) trans[i][j+]=;

             }

         }

         bool can=(A==)?dijkstra():dp();

         if(!can){

             ans|=1LL<<(t-);memcpy(trans,tmp,sizeof(tmp));

         }

     }

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

 }

 int main(){

     int i,j,k;

     //freopen("1967.in","r",stdin);

     N=rd(),A=rd(),B=rd();

     for(i=;i<=N;i++) num[i]=rd();

     solve();

     return ;

 }

巴特西

luogu3646 巴厘岛的雕塑 (dp)

最新文章

热门文章