题解 P2808 【小笼包】
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;
}