【BZOJ2306】幸福路径(动态规划,倍增)

时间:2021-06-24 21:49:37

【BZOJ2306】幸福路径(动态规划,倍增)

题面

BZOJ

题解

不要求确切的值,只需要逼近

显然可以通过移动\(\infty\)步来达到逼近的效果

考虑每次的一步怎么移动

设\(f[i][j]\)表示走\(i\)步到了\(j\)能够得到的最大权值

\(f[i][v]=max(f[i-1][u])+W[v]*p^i,(u,v)\in G\)

这样的复杂度是\(O(T(n+m))\),\(T\)是自己设定的步数

但是这样子逼近精度很慢

假设\(p=0.999999\),大概要\(10^7\)步才能达到目标进度

这样子显然太慢

我们考虑如何优化

既然一步步走很慢,那么我们考虑倍增来走

首先预处理以下两个点之间的连通性

设\(g[i][j][k]\)表示走了\(2^k\)步后是否能从\(i\)到\(j\)

那么,\(f[i][j]\)表示走了\(2^i\)步到达\(j\)能够拿到的最大权值

这样子每次随意枚举两个点\(i,j\)来转移,发现有些东西没法记录

比如枚举两个点,但是不能保证这两个点之间的最优路径是拼接在一起的

所以我们加一维\(f[i][j][l]\)表示从\(i\)到\(j\)走了\(2^l\)步拿到的最优权值

枚举一个中间点\(k\)

\(f[i][j][l]=max(f[i][k][l-1]+p^{2^{l-1}}f[k][j][l-1])\)

这样子的复杂度就是\(O(n^3log10^7)\)了

其实\(g\)也可以不用预处理是否联通,直接把不连通的距离设为\(-inf\)就行了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 111
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
struct Line{int v,next;}e[MAX<<4];
int h[MAX],cnt=1;
inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}
int n,m,S;
double f[30][MAX][MAX];
double W[MAX],p,Ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%lf",&W[i]);
scanf("%d",&S);scanf("%lf",&p);
memset(f,0xfe,sizeof(f));
for(int i=1;i<=n;++i)f[0][i][i]=0;
for(int i=1;i<=m;++i)
{
int u=read(),v=read();
f[0][u][v]=W[v]*p;
}
for(int l=1;l<30;++l,p*=p)
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[l][i][j]=max(f[l][i][j],f[l-1][i][k]+p*f[l-1][k][j]);
for(int i=1;i<=n;++i)Ans=max(Ans,f[29][S][i]);
printf("%.1lf\n",Ans+W[S]);
return 0;
}