题解
这题很厉害。我也是看了题解才知道怎么做的。
（官网日文真心看不懂）
（如果日语学的很6的话可以看这里：链接）
我们看到这道题，首先想到的是什么？
对！就是
爆搜。
…
先留着这个看似不切实际的想法。我们暴力算排列，然后$O(n^2)$算结果，复杂度不用想，肯定上天。
然后观察：$D$最大不过$7$，然后我们又有上面那个算法，
所以现在考虑用这个条件来优化转移。
设$dp(i,Perm)$，其中$Perm$表示从$i-maxd+1$吃到第$i$个小笼包的顺序，$i$表示当前正在处理第$i$个。
则这样就可以状态转移了，每一次向前推进一位，然后对于前面的排列，我们试图插入新的小笼包，并且计算新的小笼包在其中造成的贡献。（被泼到，泼别的）
时间复杂度
（官方说是$P$一个多项式，算了也别管了）
这种新的状压方式学到了。
不过可能看的时候会有疑问：$k$为什么会到$7$呢？
还是要考虑到原来整个排列全被枚举的情况。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
typedef long long ll;
int f[2][7000000]={0},permu[10],permu2[10];//在第i次吃第j个小笼包
int n,d[105],a[105];
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
void init_permu(){
for(int j=0;j<7;j++)
permu[j]=j;
}
int ptoi(int *L){
int res=0;
for(int i=0;i<7;i++)
res=res*10+L[i];
return res;
}
void init(){
n=read();
for(int i=0;i<n;i++)d[i]=read();
for(int i=0;i<n;i++)a[i]=read();
}
void solve(){
for(int i=0;i<n;i++){
init_permu();
int B=(i&1),B_=(B^1),cnt,code1,code2;
do{
code1=ptoi(permu);
for(int k=0;k<=7;k++){
//枚举新加入的位置
cnt=0;
int contribution=0;
//在第i个被吃掉之前他被泼到的
for(int kk=0;kk<k;kk++){
int loc=i-1-permu[kk];
if(loc>=0&&permu[kk]+1<=d[loc])
contribution+=a[loc];
if(permu[kk]<6)
permu2[cnt++]=permu[kk]+1;
}
permu2[cnt++]=0;
//在第i个被吃掉之后他被泼到的
for(int kk=k;kk<7;kk++){
int loc=i-1-permu[kk];
if(loc>=0&&permu[kk]+1<=d[i])
contribution+=a[i];
if(permu[kk]<6)
permu2[cnt++]=permu[kk]+1;
}
code2=ptoi(permu2);
f[B_][code2]=max(f[B_][code2],f[B][code1]+contribution);
}
f[B][code1]=0;
}while(next_permutation(permu,permu+7));
}
int ans=0;
init_permu();
do{
ans=max(ans,f[n&1][ptoi(permu)]);
}while(next_permutation(permu,permu+7));
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}