题目大意

有 $N$（$N \le 18$）个池子，第 $i$ 个池子每秒积攒 $m_i$ 点法力（在第 $0$ 秒时，所有池子都是 $0$ 点法力）。

另外还有 $M$ 条有向边，第 $i$ 条有向边 $(a_i,b_i,t_i)$ 表示从第 $a_i$ 个池子到第 $b_i$ 个池子需要 $t_i$ 秒。

接下来给出 $Q$ 组询问，每组询问由 $s$ 和 $e$ 组成，询问一个人从任意池子开始，在第 $s$ 秒结束时在第 $e$ 个池子处，期间能收集最多多少点法力。

分析

首先我们会意识到一个问题，这个人可能会走来走去的，以至于一个池子经过特别多次，这种情况过于繁琐，我们是不想看到的，所以我们考虑简化问题为：只记录每个池子最后一次经过的时间。这样正确性是显然的。

但是这样不一定能恰好用完 $s$ 秒，那么贪心地想，固定经过池子的顺序后，显然到达每个池子的时间越晚越好。另外，两个池子之间走最短路也是最优的。

具体地，假设 $p_1$，$p_2 \dots p_k$ 表示依次经过的 $k$ 个池子，设 $dist(i,j)$ 表示池子 $i$ 到池子 $j$ 的最短时间，则根据贪心策略：最后离开池子 $p_i$ 的时间 $time_i$ 最好为 $s-\sum_{j=i}^{k-1}dist(p_j,p_{j+1})$。

故当固定 $p$ 数组和 $s$ 后，答案为：$\sum_{i=1}^k time_im_{p_i}$。但由于 $p$ 数组和 $s$ 都是未知的，且 $s$ 是作为询问给出的，不好处理，所以考虑先将 $s$ 分离出来，将式子改写：

$\begin{aligned} 原式 &=\sum_{i=1}^{k} (s-\sum_{j=i}^{k-1} dist(p_j,p_{j+1}))m_{p_i}\\ &= s\sum_{i=1}^km_{p_i}-\sum_{i=1}^k(m_{p_i}\sum_{j=i}^{k-1}dist(p_j,p_{j+1}))\\ \end{aligned}$

这样的话，$s$ 就只和 $p$ 数组中元素所构成的集合有关了，且对于每个集合，式子后半部分的最小值是可以通过 dp 求解的。

于是，我们设 $sum_S=\sum\limits_{i \in S}m_i$

再设 $f_{i,S}$ 表示目前走到 $i$，走过的集合为 $S$，式子后半部分的最小值。

转移时枚举上一步从哪个点走来 $i$ 即可：

（记 $S'$ 表示 $S$ 除掉元素 $i$ 后的集合）

$f_{i,S}=\min\limits_{j \ne i,j \in S}(f_{j,S'}+dist(j,i)sum_{S'})$

可以在 $O(n^22^n)$ 时间内处理 $f$。

处理完后会发现对于每一组询问 $s$，$e$，我们要算的是下式：

$\max\limits_{S \ni e}(s\times sum_S-f_{e,S})$

直接算是 $O(2^n)$ 的，考虑优化。

套路性地按 $e$ 分类后，对于每一个集合 $S$ 构造一条斜率为 $sum_S$，截距为 $-f_{e,S}$ 的直线。并将每一个询问的 $s$ 看作变化的 $x$，每次询问所有直线在 $x$ 处的最大值。李超线段树维护即可。时间复杂度 $O(2^nn^2+n2^n\log q+q\log q)$

注意：①最好将所有的 $s$ 先离散化，不然空间容易炸；②注意 INF 的值不能设的太小。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=18,MaxN=1e9,MaxS=1<<18,Q=2e5,INF=1e18;
int	n,m,q;
int a[N+5];
int G[N+5] [N+5];
int sum[(1<<N)+5],f[N+5] [MaxS+5];
int s[Q+5],e[Q+5],val[Q+5];
struct LC_Tree{
	int tot;
	int tag[MaxS<<2];
	struct line{
		int k,b;
	}p[MaxS+5];
	void make_line(int _k,int _b){
		++tot;
		p[tot].k=_k,p[tot].b=_b;
	}
	int Calc(int id,int pos){
		return p[id].k*pos+p[id].b;
	}
	void update(int now,int L,int R,int id){
		int orig=tag[now];
		int mid=L+R>>1;
		int lson=now<<1,rson=(now<<1)|1;
		if(Calc(id,val[mid])>Calc(orig,val[mid]))
			swap(id,orig);
		tag[now]=orig;
		if(L==R)
			return ;
		if(Calc(id,val[L])>Calc(orig,val[L]))
			update(lson,L,mid,id);
		if(Calc(id,val[R])>Calc(orig,val[R]))
			update(rson,mid+1,R,id);
	}
	int query(int now,int L,int R,int pos){
		if(L==pos&&pos==R)
			return Calc(tag[now],val[pos]);
		int mid=L+R>>1;
		int lson=now<<1,rson=(now<<1)|1;
		if(pos<=mid)
			return max(Calc(tag[now],val[pos]),query(lson,L,mid,pos));
		return max(Calc(tag[now],val[pos]),query(rson,mid+1,R,pos));
	}
}tr[N+5];
void initG(){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			if(i==j)
				G[i] [j]=0;
			else G[i] [j]=INF;
		}
}
void floyd(){
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				G[i] [j]=min(G[i] [j],G[i] [k]+G[k] [j]);
}
void work_f(){
	for(int S=1;S<=(1<<n)-1;++S)
		for(int i=1;i<=n;++i)
			if(S&(1<<n-i))
				sum[S]+=a[i];
	for(int S=1;S<=(1<<n)-1;++S)
		for(int i=1;i<=n;++i){
            f[i] [S]=INF;
			if(S&(1<<n-i)){
				int tS=S^(1<<n-i);
				if(tS==0){
					f[i] [S]=0;
					continue;
				}
				for(int j=1;j<=n;++j)
					if(tS&(1<<n-j))
						if(G[j] [i]!=INF)
							f[i] [S]=min(f[i] [S],f[j] [tS]+G[j] [i]*sum[tS]); 
			}
		}
}
void prepare_line(){
	for(int i=1;i<=n;++i){
		tr[i].tot=-1;
		tr[i].make_line(0,-INF);
		for(int S=1;S<=(1<<n)-1;++S)
			if(f[i] [S]<INF){
				tr[i].make_line(sum[S],-f[i] [S]);
				tr[i].update(1,1,q,tr[i].tot);
			}
	}
}
signed main(){
	//freopen("monster.in","r",stdin);
	//freopen("monster.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	initG();
	for(int i=1;i<=m;++i){
		int u,v,w;
		cin>>u>>v>>w;
		G[u] [v]=w;
	}
	floyd();
	work_f();
	cin>>q;
	for(int i=1;i<=q;++i){
		cin>>s[i]>>e[i];
		val[i]=s[i];
	}
	sort(val+1,val+1+q);
	prepare_line();
	for(int i=1;i<=q;++i){
		s[i]=lower_bound(val+1,val+1+q,s[i])-val;
		cout<<tr[e[i]].query(1,1,q,s[i])<<'\n';
	}
	return 0;
}