NOIP模拟题 期望DP 礼物

大家都很强，可与之共勉。

Description

夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生日礼物。
商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种礼物的喜悦值不能重复获得）。
每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。季堂每次都会将店员拿出来的礼物买下来。
众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。
求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期望购买次数。

Input

第一行，一个整数N，表示有N种礼物。
接下来N行，每行一个实数Pi和正整数Wi，表示第i种礼物被拿出来的概率和可以获得喜悦值。

Output

第一行，一个整数表示可以获得的最大喜悦值。
第二行，一个实数表示获得这个喜悦值的期望购买次数，保留3位小数。

Sample Input

3
0.1 2
0.2 5
0.3 7

Sample Output

14
12.167

Data Constraint

对于10%的数据，N=1
对于30%的数据，N≤5
对于100%的数据，N≤20,0

Solution

我们发现N≤20，于是我们果断状压DP。
设状态s,表示买走了哪些物品。依题意，得方程：

移项

# include <cstdio>

int w [21] ;
double dp [1 << 21], p [21], sig ;

int main ( )  {
    freopen ( "gift.in", "r", stdin ) ;
    freopen ( "gift.out", "w", stdout ) ;
    int n ;
    scanf ( "%d", & n ) ;
    register int i, j, l ;
    for ( i = 1 ; i <= n ; ++ i )   scanf ( "%lf%d", p + i, w + i ) ;
    long long ans ( 0 ) ;
    for ( i = 1 ; i <= n ; ++ i )   if ( w [i] )    ans += w [i] ;
    for( i = 1, l = ( 1 << n ) - 1 ; i <= l ; ++ i )  {
        sig = 0 ;
        dp [i] = 0 ;
        for ( j = 1 ; j <= n ; ++ j )  {
            if( i & ( 1 << ( j - 1 ) ) )  {
                dp [i] += dp [i - ( 1 << ( j - 1 ) )] * p [j] ;
                sig += p [j] ;
            }
        }       
        dp [i] = ( dp [i] + 1 ) / sig ;
    }   
    printf ( "%lld\n%.3lf\n", ans, dp [( 1 << n ) - 1] ) ;
}