BZOJ2306 [Ctsc2011]幸福路径[倍增]

这个有环的情况非常的讨厌，一开始想通过数学推等比数列的和，但是发现比较繁就不做了。

然后挖掘这题性质。

数据比较小，但是体力可以很接近1（恼怒），也就是说可能可以跳很多很多步。算了一下，大概跳了2e7次左右这个体力才缩到1e-14左右，这时已经几乎不会影响答案惹。也就是说，点比较少，有没有暴力做法？
发现从一个点假设满体力开始跳若干步，有最大价值的方案，如果前面一个点跳若干步过来，再在这个点以某个$x∈(0,1)$的体力开始，那么原来的最大的方案还是最大的，只要乘上一开始这个体力就好了。这说明答案可以用类似dp的方式逼近。

然后看这个跳非常多步还可以dp就反应到了倍增跳跃的模型。设$f[i][j][k]$为从$i$到$j$跳$2^k$步最大价值。然后可以倍增推了。

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

这个是$O(n^3 logn)$的，log那个是自己调的，25左右为宜。

由于是个人想的，所以实现上比较清奇。后来看了说本质就是个floyd。。感觉我理解还不够深入呃，如果谁知道为什么换一下枚举顺序就可以滚动了，烦请赐教。

另外有一个坑暂时不知道为什么，line34初始化要先给没有自环的连上自环，价值0。以后可能会请教别人这个地方，在座各位如果知道为什么这样还望不吝赐教。。

2019.9.29 UPD：从神仙hkk处获取了为什么要给所有点都连自环$0$：如果是下面这组数据：

0.5

hack!!

显然有问题。因为，这里的路是有尽头的，需要跳三步，而没办法有一个状态有效表示跳3步，不妨改变状态设计，设$f[i][j][k]$为从$i$到$j$跳最多$2^k$步最大价值。然后$f_{1,4,2}$就可以表示这个答案，而原来答案是没法表示的，但又因而引出这个$2^2$步的最后一步没办法再跳的问题，也就是在$4$号点没路了。这时候如果按照原来的dp方法，转移$f_{1,4,2}=f_{1,3,1}+p^2f_{3,4,1}$，但是这里的$f_{3,4,1}$按照新定义是可以有值的，如果直接用之前dp方程dp，会因为$f_{3,4,1}$没有值而出错，原因在于$f_{3,4,1}$最大时是$3\to 4$跳$2^0$步，满足新的定义，但是没法保留到$f_{3,4,1}$，这要求我们手动给$3$或者$4$添加一个0的自环保证可以按新定义正常转移。这样，就不会出现$2$的整数次方跳不完，后半截没有值而出错的情况。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<bitset>

 #define dbg(x) cerr << #x << " = " << x <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=;

 db f[N][N][];

 db fp[],A[N],p,ans;

 int n,m,s;

 inline db fpow(db x,int k){db ret=;for(;k;k>>=,x*=x)if(k&)ret*=x;return ret;}

 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);

     read(n),read(m);

     for(register int k=;k<=;++k)

         for(register int i=;i<=n;f[i][i][k]=,++i)

             for(register int j=;j<=n;++j)

                 f[i][j][k]=-0x3f3f3f3f;

     for(register int i=;i<=n;++i)scanf("%lf",&A[i]);

     read(s);scanf("%lf",&p);

     for(register int i=;i<=;++i)fp[i]=fpow(p,<<i);

     for(register int i=,x,y;i<=m;++i)read(x),read(y),f[x][y][]=A[y]*p;

     for(register int k=;k<=;++k)

         for(register int i=;i<=n;++i)

             for(register int l=;l<=n;++l)

                 for(register int j=;j<=n;++j)

                     MAX(f[i][j][k],f[i][l][k-]+fp[k-]*f[l][j][k-]);

     for(register int j=;j<=n;++j)MAX(ans,f[s][j][]);

     ans+=A[s];printf("%.1lf\n",ans);

     return ;

 }

巴特西

BZOJ2306 [Ctsc2011]幸福路径[倍增]

最新文章

热门文章