P4308

$n$ 非常小，所以我們考慮佛洛德，然後又發現這個 $p^k$ 在 $k$ 很大的時候就很小了，接近於$0$，所以我們可以搞一個很大的 $k$ ，例如 $2^200$ 次方，所以可以使用倍增

那我們就設 $dp_{l,i,j}$ 表示我們從 $i$ 走到 $j$ 走 $2^l$ 步，然後我們 $l$ 直接開到 $200$ 就行了

#include<iostream>
#include<iomanip>
#include<cstdio>
#define int long long
#define N 105
using namespace std;
bool Test_MLE_start;
int _=1,n,m,s,now=1;double p,w[N],fac[205],dp[205][N][N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("D.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int l=0;l<=200;l++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i!=j) dp[l][i][j]=-1e18;
				}
			}
		}for(int i=1;i<=n;i++) cin>>w[i];s=reads(),cin>>p;
		for(int i=1;i<=m;i++){
			int u,v;u=reads(),v=reads();
			dp[0][u][v]=w[v]*p;
		}fac[0]=p;
		for(int i=1;i<=200;i++) fac[i]=fac[i-1]*fac[i-1]; 
		for(int l=1;l<=200;l++){
			for(int k=1;k<=n;k++){
				for(int i=1;i<=n;i++){
					for(int j=1;j<=n;j++){
						dp[l][i][j]=max(dp[l][i][j],dp[l-1][i][k]+dp[l-1][k][j]*fac[l-1]*1.0);
					}
				}
			}
		}double ans=0;
		for(int i=1;i<=n;i++) ans=max(ans,dp[200][s][i]);
		cout<<fixed<<setprecision(1)<<ans+w[s]<<"\n";
	}
	return 0;
}

做法

注意到 $n$ 比较小，所以想到 Floyd 算法。首先有一个比较暴力的思路就是在状态中加入一个 $l$ 表示走过的路径数。但是路径可能很长，所以这样不可行。所以我们想到倍增这个步数 $l$。设计 $dp[l][i][j]$ 表示从 $i$ 到 $j$ 走 $2^l$ 步，幸福值最大是多少。

我们的 $l$ 可以遍历到 $200$，这样就算 $\rho$ 高达 $0.999999$，它的 $2^{200}$ 次方也不过是 $10^{-6.88\times 10^{53}}$，和 $0$ 基本无差别。不需要担心精度问题。

每一次使用 $dp[l-1][i][k]+p^{l-1}\times dp[l-1][k][j]$ 更新 $dp[l][i][j]$ 即可。初值为 $dp[l][i][i]$ 为 $0$，其余为极小值，这是因为路径可能没走到 $2$ 的整数次幂就停止了，需要补足到 $2^l$。

然后对于每一条边 $(i,j)$， 令 $dp[0][i][j]=p\times w[j]$。

然后他没有算上起点，所以要加上。答案就是 $w[s]+\max_{i=1}^n dp[200][s][i]$。

复杂度 $\Theta(Ln^3)$，其中 $L$ 表示倍增上限，我设置的 $200$。足以通过本题。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,L=205;
int n,m,s;
double w[N],p,ans;
vector<int>G[N];
double dp[L][105][105];
double fac[L];
signed main() {
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; ++i) {
		cin>>w[i];
	}
	for(int l=0; l<L; ++l) {
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				if(i!=j)dp[l][i][j]=-1e18;
			}
		}
	}
	cin>>s>>p;
	fac[0]=p;
	for(int i=1; i<L; ++i) {
		fac[i]=fac[i-1]*fac[i-1];
	}
	for(int i=1,x,y; i<=m; ++i) {
		cin>>x>>y;
		dp[0][x][y]=w[y]*p;
	}
	for(int l=1; l<L; ++l) {
		for(int k=1; k<=n; ++k) {
			for(int i=1; i<=n; ++i) {
				for(int j=1; j<=n; ++j) {
					dp[l][i][j]=max(dp[l][i][j],dp[l-1][i][k]+fac[l-1]*dp[l-1][k][j]);
				}
			}
		}
	}
	for(int i=1; i<=n; ++i) {
		ans=max(ans,dp[L-1][s][i]);
	}
	cout<<fixed<<setprecision(1)<<w[s]+ans<<"\n";
	return 0;
}