记录编号	246062	评测结果	AAAAAAAAAA
题目名称	[APIO2015]巴厘岛的雕塑	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	1.067 s
提交时间	2016-04-04 21:55:22	内存使用	11.90 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=2010;
bool f[maxn][maxn],g[maxn][maxn],del[maxn][maxn];
//del指一段区间和是否可取，g指一个dp决策是否可取
bool G[maxn];
int F[maxn];
//这里针对特殊数据改变DP方式，表示到当前位置最小分段的方案数
long long sum[maxn],ans;
int n,A,B,Maxk;
int main(){
    freopen("sculpture.in","r",stdin);
    freopen("sculpture.out","w",stdout);
    scanf("%d%d%d",&n,&A,&B);
    for(int i=1;i<=n;i++){
        scanf("%lld",&sum[i]);
        sum[i]+=sum[i-1];
    }
    if(A>1){
        for(int k=47;k>=0;k--){
            memset(f,0,sizeof(f));
            f[0][0]=true;
            for(int i=1;i<=n;i++)
                for(int j=0;j<i;j++)
                    for(int l=1;l<=B;l++)
                        if(!g[j][l-1]&&f[j][l-1]&&!((sum[i]-sum[j])&(1ll<<k))&&!del[j+1][i])
                            f[i][l]=true;
            
            bool flag=false;
            for(int l=A;l<=B;l++)
                if(f[n][l]&&!g[n][l])
                    flag=true;
            if(flag){
                for(int i=1;i<=n;i++)
                    for(int l=1;l<=B;l++)
                        if(!f[i][l])
                            g[i][l]=true;
                            
                for(int i=1;i<=n;i++)
                    for(int j=0;j<i;j++)
                        if((sum[i]-sum[j])&(1ll<<k))
                            del[j+1][i]=true;
            }
            else
                ans+=1ll<<k;
        }
    }
    else{
        for(int k=47;k>=0;k--){
            memset(F,127,sizeof(F));F[0]=0;
            for(int i=1;i<=n;i++)
                for(int j=0;j<i;j++)
                    if(F[j]!=2139062143&&!del[j+1][i]&&!G[j]&&!((1ll<<k)&(sum[i]-sum[j])))
                        F[i]=min(F[i],F[j]+1);
            
            bool flag=false;            
            if(!G[n]&&F[n]<=B)
                flag=true;
            
            if(flag==true){
                for(int i=1;i<=n;i++)
                    for(int j=0;j<i;j++)
                        if(F[i]>B)
                            G[i]=true;
                
                for(int i=1;i<=n;i++)
                    for(int j=0;j<i;j++)
                        if((1ll<<k)&(sum[i]-sum[j]))
                            del[j+1][i]=true;
            }        
            else        
                ans+=1ll<<k;
        }
    }
    printf("%lld\n",ans);
    return 0;
}