【BZOJ2306】幸福路径（动态规划，倍增）

题面

题解

不要求确切的值，只需要逼近
显然可以通过移动(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
",Ans+W[S]);
	return 0;
}