模拟赛里遇到的，差一点做出来
感觉是好题
题目链接
题意
现在有一个 个点 条边的有向图，边有边权。
每一个点都是一个井，第
个井每秒会出现
的法力，并积攒在这个井里。
wyr
每一时刻可以选择站在原地不动或者沿着一条边走动（所用的时间为这条边的边权）。
当 wyr 到达一个井的时候，他就可以把这个井目前的所有法力收集起来。
进行 次询问，每一次询问给出
，wyr
想知道如果他从任何一个节点出发，经过 秒后到达点 ，最多能够收集多少法力。
题解
感觉是小结论题，但是结论都不算难想。
首先我们发现，假如一个节点被经过多次，那么显然只有最后一次经过是有用的，因为在这个节点收集的法力数量之和最后一次在这个节点的时间有关。
所以我们可以强制规定每一个节点只被经过一次，预处理的时候跑一个 Floyd
就好了。
然后继续找结论，我们会发现，wyr 只会选择在起点停留。
如果 wyr
在中途的某个点停留了，我们完全可以把停留的时间放到起点，这样显然更优。
考虑进行 dp，设
表示目前经过了
这些点，最后一个经过的点为
且总时间为 ，最多能收集多少法力。
这一维范围为 ，所以想要 dp
的话，一定要把时间这一个维度压掉。
想要压掉时间这一个维度，首先会面临一个问题，那就是我们现在往路径后面新加入一个点，我们无法计算新得到的法力。
那么我们换一下状态，设 表示会有多少法力浪费掉， 表示这样走总时间是多少。
那么现在对于每一组询问，我们便得到答案 。
其中 ，即
中所有点，一秒内产生的法力和。
这里可能会有一点小问题，在 dp
的过程中，法力浪费最少的方案，并不一定是最短路。
那么假如存在一个状态 ，有
，但是最短路 ，答案是不是就算大了呢？
其实答案并不会变大。
因为如果有 ，此时在起点收集到的法力数量是负数，那么一定就存在一个更优的方案，所以答案不会算大。
好，这个样子我们就得到了一个时间复杂度为 的算法，原比赛应该可以拿到
的分数。
考虑优化后面查询答案的过程。
从上面的答案可以看出，对于一个状态 和终点 ，它的答案实际上是一个关于 的函数 ，其中斜率 和截距 均为定值。
所以对于一组询问，我们实际上在查所有 构成的凸包上，对应横坐标的点。
使用李超线段树或者单调栈维护凸包即可。
我是用的是单调栈，时间复杂度为 。
代码
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int sta[262144],top;
ll P[262144];
int t[200001];
int e[200001];
ll qans[200001];
ll dis[20][20];
ll tim[262144][18];
ll dp[262144][18];
ll f[262144];
ll s[262144];
int id[262144];
ll a[20];
int n,m,q;
inline int get(int t)
{
int ans=0;
for(int i=131072;i;i>>=1) if(ans+i<=top&&P[ans+i]<=t) ans+=i;
return sta[ans];
}
int main()
{
n=read(),m=read();
memset(dis,0x3f,sizeof(dis));
for(int i=0;i<n;i++)
{
dis[i][i]=0,a[i]=read();
for(int j=0;j<(1<<n);j++) if(j&(1<<i)) s[j]+=a[i];
}
for(int i=1;i<=m;i++)
{
int u=read()-1,v=read()-1;
dis[u][v]=read();
}
for(int j=0;j<n;j++) for(int i=0;i<n;i++) for(int k=0;k<n;k++)
dis[i][k]=min(dis[i][k],dis[i][j]+dis[j][k]);
memset(dp,0x3f,sizeof(dp));
for(int i=0;i<n;i++) dp[1<<i][i]=0;
for(int i=0;i<(1<<n);i++) for(int j=0;j<n;j++) if(i&(1<<j))
{
for(int k=0;k<n;k++) if(j!=k&&(i&(1<<k)))
{
__int128 val=dp[i^(1<<j)][k]+(__int128)dis[k][j]*s[i^(1<<j)];
if(val<dp[i][j])
{
tim[i][j]=tim[i^(1<<j)][k]+dis[k][j];
dp[i][j]=val;
}
}
}
for(int i=0;i<(1<<n);i++) id[i]=i;
sort(id,id+(1<<n),[](int a,int b){ return s[a]<s[b];});
q=read();
for(int i=1;i<=q;i++) t[i]=read(),e[i]=read()-1;
for(int i=0;i<n;i++)
top=0;
for(int p=0;p<(1<<n);p++) if(id[p]&(1<<i))
{
int j=id[p];bool flag=1;
while(top)
{
int &q=sta[top];
if(dp[q][i]>=dp[j][i]) top--;
else
{
if(s[j]==s[q])
{
flag=0;
break;
}
ll x=(dp[j][i]-dp[q][i]+s[j]-s[q]-1)/(s[j]-s[q]);
if(x<=P[top]) top--;
else break;
}
}
if(flag)
{
if(!top) P[top+1]=0;
else
{
int q=sta[top];
P[top+1]=(dp[j][i]-dp[q][i]+s[j]-s[q]-1)/(s[j]-s[q]);
}
sta[++top]=j;
}
}
for(int j=1;j<=q;j++) if(e[j]==i)
{
int v=get(t[j]);
qans[j]=t[j]*s[v]-dp[v][i];
}
}
for(int i=1;i<=q;i++) printf("%lld\n",qans[i]);
return 0;
}
|
感谢观看！