受到样例的第四个询问启发，我们可以发现一个性质：一开始先让魔力积累，然后肯定是在最晚的那个时候，我们去把魔力池里该取的魔力取走，而不是一开始就和一个无头苍蝇一样在图上乱走。
比如你像无头苍蝇一样走了一个路径：\(1\rightarrow3\rightarrow2\rightarrow4\rightarrow2\rightarrow3\rightarrow4\rightarrow2\rightarrow3\)，那你会发现我还不如先一直待在一号点，然后快结束的时候，我再去走\(1\rightarrow4\rightarrow2\rightarrow3\)这样的路径来的好，同时，我即使途径\(3\)号点和\(2\)号点，我一开始也可以假装没取，反正之后我还要再经过它。
由于有我们上面的发现，现在我可以假设每个点都只会取走一次魔力值，\(N\)很小，所以可以状压\(S\)表示取走了\(S\)池子里的魔力值。
任选一个时刻作为终点时刻，不妨假设是\(x\)。
\(f[i][S]\)表示在最后时刻\(x\)我们位于\(i\)号点，走过了\(S\)这些点，取得的最大魔力值是多少。用\(sum[S]\)表示\(S\)集合单位时间积累的魔力之和，用\(dist[a][b]\)表示\(a\)到\(b\)的最短路径和。
\(f[i][S]=max(f[j][S-\{i\}]-sum[S-\{i\}]\times dist[j][i])+m[i]x\)
你会发现，对于一个状态\(S\)，它可能有一些点被推到负时刻去了，这会不会对答案产生不利呢？答案是不会，因为对于推到负时刻去的情况，我们把这几个点给删除，会使得更小的集合\(S'\)答案更优。
对于询问时刻\(s\)，我们要做的是找出一个状态\(f[e][S]\)，给这个状态加上\((s-x)\times sum[S]\)，求最大值，直接枚举\(S\)会超时，所以我要用数据结构来维护一次函数极值，这个过程很简单，每次往数据结构中插入一条线，将他和已经在数据结构中的线构成的交点进行比较，将小于它的一连串交点pop出去，换上属于自己的交点，找小于它的交点用二分法。也可以用类似求凸包的方法，将所有的直线按斜率升序排列，用栈维护每个直线掌管的区间，可以做到\(O(n2^n)\)。
由于\(x\)时刻可以任选，所以这里直接选取\(x=0\)进行\(dp\)
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 28;
long long a[maxn];
long long dist[maxn][maxn];
long long f[19][(1<<18)+10],sum[(1<<18)+10];
struct line{
long long k,b;
};
int cmp(line alpha,line beta){
if(alpha.k == beta.k) return alpha.b > beta.b;
else return alpha.k < beta.k;
}
struct HotterColder{
line l[(1<<18)+10];
struct node{
int l,r;
int nb; // left right number
}p[(1<<18)+10];
int size,size2;
long long getdata(int now,int x){
return l[now].k*x+l[now].b;
}
void getres(){
sort(l+1,l+size+1,cmp);
for(int i=1;i<=size;i++){
if(i != 1 && l[i].k == l[i-1].k) continue;
while(size2 && getdata(i,p[size2].l) >= getdata(p[size2].nb,p[size2].l)){
size2--;
}
if(size2 == 0){
p[++size2] = (node){0,(int)1e9,i};
}else{
int kk = p[size2].nb;
long long bhpts = (l[kk].b-l[i].b)/(l[i].k-l[kk].k)+((l[kk].b-l[i].b)%(l[i].k-l[kk].k)!=0);
if(bhpts>1e9) continue;
p[size2].r = bhpts-1;
p[++size2] = (node){bhpts,(int)1e9,i};
}
}
}
void add(int k,long long b){
l[++size] = (line){(long long)k,b};
}
long long query(int x,int ll,int r){
int mid = (ll+r)/2;
if(p[mid].l <= x && p[mid].r >= x){
return getdata(p[mid].nb,x);
} else if(p[mid].l > x) return query(x,ll,mid-1);
else return query(x,mid+1,r);
}
}H[20];
int main(){
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j] = 1e9+1; //注意这个上界对求真正的dist是远远不够的，但这道题这样就足够了
//想一想原因^o^
for(int i=1;i<=n;i++) dist[i][i] = 0;
for(int i=1;i<=m;i++){
int u,v,w; cin >> u >> v >> w;
dist[u][v] = w;
}
//floyd
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
for(int S=0;S<(1<<n);S++){
for(int i=1;i<=n;i++){
f[i][S] = -3e18;
if((1<<i-1)&S){
sum[S] = sum[S-(1<<i-1)]+a[i];
}
}
}
//dp,假设终止点为0
for(int i=1;i<=n;i++) f[i][(1<<i-1)] = a[i]*0;
for(int S=1;S<(1<<n);S++){
for(int i=1;i<=n;i++){
if((1<<i-1)&S){
for(int j=1;j<=n;j++){
if(((1<<j-1)&S) && i!=j && dist[j][i]<2e15){
f[i][S] = max(f[i][S],f[j][S-(1<<i-1)]-sum[S-(1<<i-1)]*dist[j][i]);
}
}
}
}
}
int q; cin >> q;
for(int i=1;i<=n;i++){//设计构建维护一次函数的极值结构
for(int j=0;j<(1<<n);j++){
if((1<<i-1)&j) H[i].add(sum[j],f[i][j]);
}
H[i].getres();
}
for(int i=1;i<=q;i++){
long long s,e; cin >> s >> e;
long long ans = H[e].query(s,1,H[e].size2);//直接查询
/*long long ans = 0;
for(int j=0;j<(1<<n);j++){
if((1<<e-1)&j)
ans = max(ans,f[e][j]+s*sum[j]);
}*/
cout<<ans<<endl;
}
}