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$：如果是下面这组数据：
4 3 1 2 4 8 1 0.5 1 2 2 3 3 4
显然有问题。因为，这里的路是有尽头的，需要跳三步，而没办法有一个状态有效表示跳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 o 4$跳$2^0$步，满足新的定义，但是没法保留到$f_{3,4,1}$，这要求我们手动给$3$或者$4$添加一个0的自环保证可以按新定义正常转移。这样，就不会出现$2$的整数次方跳不完，后半截没有值而出错的情况。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<bitset> 7 #define dbg(x) cerr << #x << " = " << x <<endl 8 using namespace std; 9 typedef long long ll; 10 typedef double db; 11 typedef pair<int,int> pii; 12 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 13 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 14 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;} 15 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;} 16 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;} 17 template<typename T>inline T read(T&x){ 18 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 19 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 20 } 21 const int N=102; 22 db f[N][N][26]; 23 db fp[26],A[N],p,ans; 24 int n,m,s; 25 inline db fpow(db x,int k){db ret=1;for(;k;k>>=1,x*=x)if(k&1)ret*=x;return ret;} 26 27 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 28 read(n),read(m); 29 for(register int k=0;k<=25;++k) 30 for(register int i=1;i<=n;f[i][i][k]=0,++i) 31 for(register int j=1;j<=n;++j) 32 f[i][j][k]=-0x3f3f3f3f; 33 for(register int i=1;i<=n;++i)scanf("%lf",&A[i]); 34 read(s);scanf("%lf",&p); 35 for(register int i=0;i<=25;++i)fp[i]=fpow(p,1<<i); 36 for(register int i=1,x,y;i<=m;++i)read(x),read(y),f[x][y][0]=A[y]*p; 37 for(register int k=1;k<=25;++k) 38 for(register int i=1;i<=n;++i) 39 for(register int l=1;l<=n;++l) 40 for(register int j=1;j<=n;++j) 41 MAX(f[i][j][k],f[i][l][k-1]+fp[k-1]*f[l][j][k-1]); 42 for(register int j=1;j<=n;++j)MAX(ans,f[s][j][25]); 43 ans+=A[s];printf("%.1lf ",ans); 44 return 0; 45 }