自动搬运

查看原文

来自洛谷，原作者为

	朱江黄河 **

搬运于2025-08-24 21:41:50，当前版本为作者最后更新于2018-01-16 19:16:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

DP 我们发现当前这个包子的美味度最多只与它前后14个包子的顺序有关

于是我们用f[i][j]表示前i个包子并且最后8个吃的顺序为j的最大值

则f[i][j]=max(f[i-1][后7位和j的前7位相同的顺序]+第i个包子造成的美味值)

具体顺序实现用康托展开枚举全排列

注意在i不足8个时不用取max,并且全排列不到8位

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define maxn 105
    #define maxs 40350
    int a[maxn],d[maxn],f[2][maxs],maxd,w[10],w1[10];
    const int fac[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320};//阶乘,不够用可以再加 
    int cantor(int a[],int k){//康托展开 
        int ans=0,tmp;
        for(int i=0;i<k;i++){
            tmp=0;//记录有几个比它小的数 
            for(int j=i+1;j<k;j++){
                if(a[j]<a[i])tmp++;
            }
            ans+=tmp*fac[k-i-1];
        }
        return ans;
    }
    void uncantor(int a[],int k,int num){//逆康托展开
        int b[10];//b表示剩下的数,并且按升序排列 
        for(int i=0;i<k;i++)b[i]=i+1;
        b[k]=0;
        for(int i=0,x;i<k;i++){
            x=num/fac[k-i-1],num%=fac[k-i-1],a[i]=b[x];//x表示当前数是剩下的数中的第几个 
            for(int j=x;b[j];j++){
                b[j]=b[j+1];
            }
        }
    }
    void nextpermutation(int a[],int k){//下一个全排列 
        for(int i=k-2;i>=0;i--){
            if(a[i]<a[i+1]){//找到最后一个非降序的值 
                int j;
                for(j=k-1;j>i;j--){
                    if(a[i]<a[j])break;
                }
                a[i]^=a[j],a[j]^=a[i],a[i]^=a[j];//将最后一个非降序的数与后面第一个大于它的数互换 
                reverse(a+i+1,a+k);//将后面的数按升序排序,但因为是降序,所以反转一下就行了 
                return;
            }
        }
    }
    int calc(int w[],int k,int r){//计算美味值 
        int ans=0;
        for(int i=0,j=r-k;i<k;i++,j++){
            if(w[i]>w[k]){
                if(k-i<=d[r])ans+=a[r];
            }
            else{
                if(k-i<=d[j])ans+=a[j];
            }
        }
        return ans;
    }
    int main(){
        int n,ans=0;scanf("%d",&n);
        for(int i=0;i<n;i++)scanf("%d",d+i),maxd=max(maxd,d[i]);
        for(int i=0;i<n;i++)scanf("%d",a+i);
        for(int i=0;i<n;i++){
            int k=min(i,maxd);
            for(int j=0;j<k;j++){
                w[j]=j+1;
            }
            for(int j=1;j<=fac[k];j++,nextpermutation(w,k)){
                int x=0;
                if(i<=maxd)x=f[!(i&1)][cantor(w,k)];
                else{
                    for(int l=1;l<=k;l++)w1[l]=w[l-1];
                    for(int l=1;l<=k+1;l++){
                        w1[0]=l;
                        for(int m=1;m<=k;m++)if(w1[m]>=w1[0])w1[m]++;
                        x=max(x,f[!(i&1)][cantor(w1,k+1)]);
                        for(int m=1;m<=k;m++)if(w1[m]>w1[0])w1[m]--;
                    }
                }
                for(int l=1;l<=k+1;l++){
                    w[k]=l;
                    for(int m=0;m<k;m++)if(w[m]>=w[k])w[m]++;
                    f[i&1][cantor(w,k+1)]=max(f[i&1][cantor(w,k+1)],x+calc(w,k,i));
                    for(int m=0;m<k;m++)if(w[m]>w[k])w[m]--;
                }
            }
        }
        for(int i=0;i<fac[8];i++){
            ans=max(ans,f[!(n&1)][i]);
        }
        printf("%d",ans);
        return 0;
}