洛谷P3646 [APIO2015]巴厘岛的雕塑（数位dp）

传送门

话说莫非所有位运算都可以用贪心解决么……太珂怕啦……

一直把或运算看成异或算我傻逼……

考虑从高位到低位贪心，如果能使答案第$i$位为0那么肯定比不为$0$更优

然后考虑第$i$位是否能为$0$

设$f[i][j]$表示将前$i$个数分为$j$段，能否在最高位到第$i+1$位都与当前$ans$一致的情况下使第$i$位为0，可以的话$f[i][j]$为1，否则为0

考虑状态如何转移

如果$f[k][j-1]$为1且$sum[i]-sum[k]$的第$i$位为0则可以由$f[k][j-1]$转移到$f[i][j]$（其中$sum$表示前缀和）

考虑如何判断，如果$f[k][j-1]==1$且

（下面的$k$和上面那个$k$无关，因为变量有点多重复去了……）

$((sum[i]-sum[k])>>k|ans)== ans$（最高位到倒数第k+1位是否与ans一致）

$((S[i]-S[k])\&1<<(k-1))==0$（倒数第k位能否为0）

那么就可以转移了

对于每个$x$，若$f[n][A~B]$有至少一个为1，$ans$的第$k$位就可以为0

然后因为时间复杂度过不了最后一个子任务……所以$A=1$的时候特判一下……

具体来说就是因为段数只有上限，所以把$f$数组的第二维省掉，就能降一个n

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define ll long long

 #define inf 0x3f3f3f3f

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,:;}

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=;

 ll sum[N];int f[][],g[N];

 ll ans=,t;int n,l,r,len=;

 void solve1(){

     int x,i,j;

     for(x=len;x;--x){

         for(i=;i<=n;++i) g[i]=inf;

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

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

         if(g[j]<r){

             t=sum[i]-sum[j];

             if((t>>(ll)x|ans)==ans&&(t&1ll<<(ll)x-1ll)==) cmin(g[i],g[j]+);

         }

         ans<<=1ll;

         if(g[n]>r) ++ans;

     }

 }

 void solve2(){

     int x,i,j,k;

     for(x=len;x;--x){

         memset(f,,sizeof(f));

         f[][]=;

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

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

         for(k=;k<i;++k)

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

             t=sum[i]-sum[k];

             if((t>>(ll)x|ans)==ans&&(t&1ll<<(ll)x-1ll)==) f[i][j]=;

         }

         for(i=l;i<=r;++i)

         if(f[n][i]) break;

         ans<<=1ll;

         if(i>r) ++ans;

     }

 }

 int main(){

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

     n=read(),l=read(),r=read();

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

     sum[i]=sum[i-]+read();

     for(t=sum[n];t;t>>=) ++len;

     l==?solve1():solve2();

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

     return ;

 }

巴特西

洛谷P3646 [APIO2015]巴厘岛的雕塑（数位dp）

最新文章

热门文章