冲刺专题之 \(DP\)
\(T_A\) Helping People
题意
给定一个长为 \(n\) 序列 \(A\) , 其中有 \(q\) 个区间 \([l , r]\) 定义为 \(B_i\) , 对于每一个区间 , 其有 \(P_i\) 的概率使 \(A\) 序列从 \(l\) 到 \(r\) 之间的数增加 \(1\) . 问最后整个区间的最大值的期望。其中 , \(n \le 10^5 , q \le 5 \times 10^3\)
对于 \(\forall B_i , B_j (1 \le i , j \le q 且 i \ne j)\) $B_i \cap B_j = \varnothing 或 B_i \subseteq B_j 或 B_j \subseteq B_i $ (即对于两个区间来说，其不相交或被包含)
样例输入,输出
3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900
4.465000000
本题为 \(SPJ\) , 只要输出与正解之差 \(\le 10^{-6}\) 即可通过。
题解
一言难尽。
现在我们发现这个区间的性质完全满足建树的条件，于是我们建树，并跑树形 \(DP\)
并设一个超级原点 \(0\) 为 \([1 , n]\) , 其增加的概率为 \(0\)
我们设 \(front_i\) 为区间 \(i\) 的区间最大值。
现在考虑设 \(dp_{i , j}\) 为第 \(i\) 号节点 , 最大值为 \(front_i + j\) 的 \(\bf{概率}\) (本题的期望就是个幌子)
设 \(sum_{i , j}\) 为 \(dp_i\) 数组的前缀和。即 \(\le front_i + j\) 的总概率。
若我们枚举到 \(x\) 号节点 :
第一步
我们现在不考虑 \(x\) 会增加 \(1\) :
设 \(mid_{i , j}\) 数组的意义为第 \(i\) 号节点 ， 不考虑 \(i\) 会增加 \(1\) , 最大值为 \(front_i + j\) 的概率 .
得到初步转移:
定义 \(SUM\) 初为 : \(\prod\limits_{z \in son_x}sum[ \ z \ ][ \ front_x + i - front_z \ ]\)
\[mid[ \ x \ ][ \ i \ ] = \sum_{y \in son_x }\frac{ SUM }{ sum[ \ y \ ][ \ front_x + i - front_y \ ] } \times mid[ \ y \ ][ \ front_x + i - front_y \ ] \ \ \ (i \in [ \ 0 \ , \ q \ ]) \]\[SUM -= \frac{ SUM }{ sum[ \ y \ ][ \ front_x + i - front_y \ ] } \times mid[ \ y \ ][ \ front_x + i - front_y \ ] \](对于每一个 \(y\) 的运算之后 \(SUM\) 进行此次运算 )
当然，如果 \(sum[ \ y \ ][ \ front_x + i - front_y \ ] = 0\) 的话 ， 此时直接为 \(0\) (别问，问就是没注意错了 \(114514\) 遍，每次 \(\color{red}{WA}\) \(Test \ 20\) )
考虑此式的正确性：
\(\prod\limits_{z \in son_x}sum[ \ z \ ][ \ front_x + i - front_z \ ]\) : 这个东西意味着 对于 \(x\) 的每一个儿子 , 取的值均 \(\le front_x + i\) 的概率 ;
\(\frac{ SUM }{ sum[ \ y \ ][ \ front_x + i - front_y \ ] }\) : 是不考虑 \(y\) 区间 , 其他区间最大值均 \(\le front_x + i\) 的概率 ;
我们 \(\times mid[ \ y \ ][ \ front_x + i - front_y \ ]\) 保证了整个 \(x\) 区间 最大值为 \(y\) 区间的 \(front_x + i\)
但如果 \(SUM\) 不变的话 ， 对于两个区间 \(y , z \in son_x\) 均有最大值是 \(front_x + i\) 的情况时，
那么 \(y , z\) 均为 \(front_x + i\) 时的概率将会被计算两次。
此句减的操作是去重的过程。
第二步
我们进行考虑父区间 \(x\) 对于答案的影响。
我们发现当 \(x\) 的最大值和其某个子区间相同时 , \(i = 1 | \ | 0\) 的时候需要分讨一下 (原因下面提到)
对于 \(i \in [2 \ , \ q]\) 时显然不用再考虑那些被 \(x\) 包含却未被 \(y \in son_x\) 包含的点中有最大值。因为即使 \(x\) 选 , 也只会把上面的点变为 \(front_x + 1\) ，不会变为 \(front_x + i\) .
我们得到这样的式子:
\[dp[ \ x \ ][ \ i \ ] = mid[ \ x \ ][ \ i \ ] \times \left( 1 - P[ \ x \ ] \right) + mid[ \ x \ ][ \ i - 1 \ ] \times P[x] \]显然
但是对于 $ i = 1 , i = 0$ 情况 , 我们需要对 \(x\) 区间进行分讨了。
如果 \(x\) 区间的最大值不在其子节点区间里：
如果 \(i = 1\) 时 , \(x\) 区间进行加一时 ， 变为 \(front_x + 1\) , 最大值可能是他 , 所以这个就保证了区间最大值为 \(front_x + 1\) , 所以剩下的子区间可选的得到的概率为 :
\[dp[ \ x \ ][ \ 1 \ ] = P[ \ x \ ] \times \sum_{y \in son_x }sum[ \ y \ ][ \ front_x - front_y \ ] \]注意你会 \(+ 1\) 的 ， 所以不能超出 \(front_x\) .
对于 \(i = 0\) 时 ， 因为最大值就在已定了，所以剩下的只要选的不超过 \(front_x\) 就可以了.
\[dp[ \ x \ ][ \ 0 \ ] = \left(1 - P[ \ x \ ]\right) \times \sum_{y \in son_x }sum[ \ y \ ][ \ front_x - front_y \ ] \]如果 \(front_x\) 出现在其子区间里:
易得:
\[dp[ \ x \ ][ \ 1 \ ] = mid[ \ x \ ][ \ 0 \ ] \times P[ \ x \ ] + mid[ \ x \ ][ \ 1 \ ] \times \left( 1 - P[ \ x \ ]\right) \]\[dp[ \ x \ ][ \ 0 \ ] = mid[ \ x \ ][ \ 0 \ ] \times \left(1 - P[ \ x \ ] \right) \]\(code\)
CODE
#include <bits/stdc++.h>
#define int long long
using namespace std ;
const int N = 1e5 + 100 ;
const int M = 5e3 + 100 ;
inline int read() {
int x = 0 , f = 1 ;
char c = getchar() ;
while ( c < '0' || c > '9' ) {
f = c == '-' ? -f : f ;
c = getchar() ;
}
while ( c >= '0' && c <= '9' ) {
x = x * 10 + c - '0' ;
c = getchar() ;
}
return x * f ;
}
int st[N][20] , lg[N] ;
inline void build_ST( int n ) {
for ( int i = 2 ; i <= n ; ++ i ) {
lg[i] = lg[i >> 1] + 1 ;
}
for ( int j = 1 ; j <= lg[n] ; ++ j ) {
for ( int i = 1 ; i + ( 1 << j ) - 1 <= n ; ++ i ) {
st[i][j] = max( st[i][j - 1] , st[i + ( 1 << ( j - 1 ) )][j - 1] ) ;
}
}
}
inline int MAX_ST( int l , int r ) {
int k = lg[r - l + 1] ;
return max( st[l][k] , st[r - ( 1 << k ) + 1][k] ) ;
}
class edge {
public:
int to , next ;
}e[M] ; int head[M] , cnt ; bool vis[M] ;
inline void add( int x , int y ) {
cnt ++ ;
e[cnt].to = y ;
e[cnt].next = head[x] ;
head[x] = cnt ;
}
int n , q ;
double dp[M][M] , sum[M][M] ;
class Node {
public:
int l , r , front ;
double p ;
}b[M] ;
bool cmp( Node a , Node b ) {
if ( a.l == b.l ) return a.r > b.r ;
return a.l < b.l ;
}
void dfs_find( int x ) {
for ( int i = x + 1 ; i <= q ; ++ i ) {
if ( b[x].r < b[i].l ) break ;
if ( b[x].l <= b[i].l && b[i].r <= b[x].r && !vis[i] ) {
vis[i] = 1 ;
add(x,i) ; dfs_find(i) ;
}
}
}
void dfs( int x ) {
bool flag = 0 ;
for ( int i = head[x] ; i ; i = e[i].next ) {
dfs(e[i].to) ;
if ( b[x].front == b[e[i].to].front ) flag = 1 ;
}
long double sum0 = 1 ; bool flak = 0 ;
for ( int i = 0 ; i <= q ; ++ i ) {
long double sumi = 1 ; flak = 0 ;
for ( int j = head[x] ; j ; j = e[j].next ) {
int y = e[j].to ;
if ( b[x].front + i - b[y].front <= q )
if ( sum[y][b[x].front + i - b[y].front] > 0 )
sumi *= sum[y][b[x].front + i - b[y].front] ;
else flak = 1 ;
}
if ( !flak )
for ( int j = head[x] ; j ; j = e[j].next ) {
int y = e[j].to ;
if ( b[x].front + i - b[y].front <= q )
if ( sum[y][b[x].front + i - b[y].front] > 0 ) {
dp[x][i] += sumi / sum[y][b[x].front + i - b[y].front] * dp[y][b[x].front + i - b[y].front] ;
sumi -= sumi / sum[y][b[x].front + i - b[y].front] * dp[y][b[x].front + i - b[y].front] ;
}
}
}
for ( int i = q ; i >= 2 ; -- i ) {
dp[x][i] = dp[x][i - 1] * b[x].p + dp[x][i] * ( 1 - b[x].p ) ;
}
if ( !flag ) {
long double sum_0 = 1 ;
for ( int i = head[x] ; i ; i = e[i].next ) {
int y = e[i].to ;
if ( b[x].front - b[y].front <= q ) {
sum_0 *= sum[y][b[x].front - b[y].front] ;
}
}
dp[x][1] = ( 1 - b[x].p ) * dp[x][1] + b[x].p * sum_0 ;
dp[x][0] = ( 1 - b[x].p ) * sum_0 ;
}
else {
dp[x][1] = dp[x][0] * b[x].p + dp[x][1] * ( 1 - b[x].p ) ;
dp[x][0] = dp[x][0] * ( 1 - b[x].p ) ;
}
sum[x][0] = dp[x][0] ;
for ( int i = 1 ; i <= q ; ++ i ) {
sum[x][i] = sum[x][i - 1] + dp[x][i] ;
}
}
inline void Query_Expect() {
long double ans = 0 ;
int maxl = b[0].front ;
for ( int i = 0 ; i <= q ; ++ i ) {
ans += ( maxl + i ) * dp[0][i] ;
}
printf( "%.9Lf\n" , ans ) ;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen( "1.in" , "r" , stdin ) ;
freopen( "1.out", "w" ,stdout ) ;
#endif
n = read() ; q = read() ;
for ( int i = 1 ; i <= n ; ++ i ) {
st[i][0] = read() ;
}
build_ST( n ) ;
for ( int i = 1 ; i <= q ; ++ i ) {
b[i].l = read() ; b[i].r = read() ;
b[i].front = MAX_ST( b[i].l , b[i].r ) ;
scanf( "%lf" , &b[i].p ) ;
}
sort( b + 1 , b + q + 1 , cmp ) ;
b[0].l = 1 , b[0].r = n , b[0].p = 0 ; vis[0] = 1 ;
b[0].front = MAX_ST( 1 , n ) ;
dfs_find(0) ; dfs(0) ;
Query_Expect() ;
}