首页 > 代码库 > hdu4921 Map(状压统计)
hdu4921 Map(状压统计)
hdu4921 Map(状压统计)
题意:有10条长度不超过1000链,链上的节点有权值。我们从这些节点中选出一些节点来,若要选节点u,则u的前继都得被选进去。对于某一种选定的情况,我们能获得的权值为,选定的节点的权值和,以及一些附加值。附加值的求法为,对于每条链的同一深度的点,若选定的点的个数超过1,那么会得到的附加值为(si*xi/ci),其中si表示该层选中的点的权值和,xi为该层选中的点的个数,ci为该层的总点数。问,对于所有的选择情况,能得到的权值期望会是多少?
解法:很直观的一点,期望值=所有情况的权值和/所有的情况数。情况数很好算,所有的链长+1求乘积即可(要减去什么都不选的一种情况)。而所有的情况的权值和,我们这样算:因为同一层之间的点,选的个数会对该层产生一个影响,所以我们一层一层考虑。总共只有10条链,故考虑任何一层上的点,选或者不选的状态只有2^10种,那么我们枚举这2^10个状态,对于某一个状态,我们可以暴力算出能得到的点权和以及附加值,但是对于这个状态,它会出现在很多种选择情况当中。比如我们有两条链,链长都是3,当前考虑的是第二层的10状态(二进制1表示选,0表示不选),那么,当链1分别取前2个,前3个,链2分别取前0个,前1个。这四种都会包含第二层10的状态,因此,这个状态会在4种选择情况中贡献给权值总和,故而要将求出的点权和+附加值乘上情况数再累加到权值总和当中,每一层都考虑完了之后,问题得解。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std ; int son[11111] ; int chain[10][1111] , a[11111] ; int vis[11111] , du[11111] , len[11] ; double dfs ( int u , int step , int c ) { chain[c][step] = a[u] ; if ( son[u] == -1 ) return step + 2 ; return dfs ( son[u] , step + 1 , c ) ; } int main () { int n , m ; int T ; scanf ( "%d" , &T ) ; while ( T -- ) { scanf ( "%d%d" , &n , &m ) ; memset ( chain , 0 , sizeof ( chain ) ) ; memset ( du , 0 , sizeof ( du ) ) ; memset ( son , -1 , sizeof ( son ) ) ; for ( int i = 0 ; i < n ; i ++ ) scanf ( "%d" , &a[i] ) ; for ( int i = 1 ; i <= m ; i ++ ) { int a , b ; scanf ( "%d%d" , &a , &b ) ; son[a] = b ; du[b] ++ ; } double sum = 1 , ans = 0 ; int tot = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( du[i] == 0 ) { len[tot] = dfs ( i , 0 , tot ) ; sum *= len[tot] ; len[tot] -- ; tot ++ ; } } sum -= 1 ; // printf ( "sum = %f\n" , sum ) ; for ( int i = 0 ; i < 1000 ; i ++ ) { for ( int j = 0 ; j < 1 << tot ; j ++ ) { int flag = 0 ; double add = 0 , p = 1 , x = 0 , cnt = 0 ; for ( int k = 0 ; k < tot ; k ++ ) { if ( chain[k][i] ) cnt ++ ; if ( j & (1<<k) ) { if ( chain[k][i] == 0 ) { flag = 1 ; break ; } add += chain[k][i] ; x ++ ; p *= len[k] - i ; } else { p *= min ( len[k] + 1 , i + 1 ) ; } } if ( flag ) continue ; double fuck = ( add + (x>1?(add*x/cnt):0) ) * p ; // printf ( "i = %d , j = %d , fuck = %f\n" , i , j , fuck ) ; // printf ( "add = %lf , p = %lf , x = %lf , cnt = %lf\n" , add , p , x , cnt ) ; ans += fuck ; } } printf ( "%.3f\n" , ans / sum ) ; } return 0 ; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。