依旧使用具有“累加”意义的状态，与修长城不同的是，路过某点时不一定要累加改点的“权值”，但是每一次移动对今后所有累加的点的“权值”的影响是相同的，为此可以增加一维cnt，d(i,j,cnt,p)表示i~j的决策已经确定时，当前在p(i或者j)，从（1 ~ i-1）与（j+1）中选取cnt个所能得到的“最大收益”，状态的转移可以通过枚举第cnt中的第一个累加的点实现，假设选取的点为x，则代表x+1 ~ i-1或j+1 ~ x-1的点舍弃 ，原因在于“在任意时刻，送餐的人已经考虑过的（送了或者决定放弃订单）的客户一定是一个连续区间。不然他就路过了某一家客户，没考虑这个客户就跑了”（转载自zhangqs）。于是就有d(i,j,cnt,p)=maxd((x,j,cnt-1,0)+e[i]-abs(p[x]-p[k])*cnt),abs(p[x]-p[k]对包括x在内的今后所有cnt个点的权值都有影响。假设确定了整个行程要送多少分披萨cnt，整个动态规划过程中的状态实际上从选择第cnt个披萨到cnt-1······到选择第一个披萨转移的；d(i,j,cnt,p)值的实际意义在于后面cnt个披萨的权已经全部计算在内的最大值(除去i ~ j中运送已经确定的部分披萨对今后的影响)显然答案为d(i,i,cnt-1,0)+e[i]-abs(p[i])*cnt中的最大值,1<=i<=n,1<=cnt<=n。讨论当未决定的点不足cnt时会不会对答案产生影响：假设在某一状态时产生这种情况d(i,j,cnt1,p)，实际上哪怕是一个“合法的cnt”,未来也可能未选满cnt个，且d(i,j,cnt1,p)的最初状态来源为一个d(l,r,cnt2,p) （cnt2!=0,边界状态l=1,r=n 或者cnt=0)的d值都为0。那么d(i,j,cnt1,p)是不是可以理解成未来选择小于等于cnt1个点的最大收益了呢？这道题记忆化搜索应该是一个比较优的写法，写递推或者刷表时可能会漏掉那些看似“不合法”的状态的更新。
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std
;
int t
,n
,pos
[105],e
[105],d
[105][105][105][2],ans
;
int dp(int l
,int r
,int cnt
,int p
)
{
if(d
[l
][r
][cnt
][p
]!=-1)
return d
[l
][r
][cnt
][p
];
if(cnt
==0)
return 0;
int maxn
=0;
if(!p
){
for(int i
=1;i
<l
;i
++)
maxn
=max(maxn
,dp(i
,r
,cnt
-1,0)+e
[i
]-abs(pos
[i
]-pos
[l
])*cnt
);
for(int i
=r
+1;i
<=n
;i
++)
maxn
=max(maxn
,dp(l
,i
,cnt
-1,1)+e
[i
]-abs(pos
[i
]-pos
[l
])*cnt
);
}
else{
for(int i
=1;i
<l
;i
++)
maxn
=max(maxn
,dp(i
,r
,cnt
-1,0)+e
[i
]-abs(pos
[i
]-pos
[r
])*cnt
);
for(int i
=r
+1;i
<=n
;i
++)
maxn
=max(maxn
,dp(l
,i
,cnt
-1,1)+e
[i
]-abs(pos
[i
]-pos
[r
])*cnt
);
}
d
[l
][r
][cnt
][p
]=maxn
;
return maxn
;
}
int main()
{
cin
>>t
;
while(t
--)
{
cin
>>n
;
ans
=0;
for(int i
=1;i
<=n
;i
++)
cin
>>pos
[i
];
for(int i
=1;i
<=n
;i
++)
cin
>>e
[i
];
memset(d
,-1,sizeof(d
));
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
ans
=max(ans
,dp(i
,i
,j
-1,0)+e
[i
]-abs(pos
[i
])*j
);
cout
<<ans
<<endl
;
}
}
