【NOIP2016提高A组8.12】礼物

题目

夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生日礼物。

商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种礼物的喜悦值不能重复获得）。

每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。季堂每次都会将店员拿出来的礼物买下来。

众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。

求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期望购买次数。

分析

首先，因为Wi>0,显然最大喜悦值为全选的情况。

注意到n“肥”常小。

考虑状压dp。

设S是二进制表示哪些礼物买过，\(F_S\)表示期望。

从后往前推，



然后移项得



这是出题人的标程

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std ;

#define N 2000000 + 10

typedef long long ll ;

double f[N] , P[N] ;

int n , m ;

ll ans ;

int main() {

	scanf( "%d" , &n ) ;

	for (int i = 1 ; i <= n ; i ++ ) {

		int a ;

		scanf( "%lf%d" , &P[i] , &a ) ;

		if ( P[i] > 0 ) ans += a ;

	}

	m = (1 << n) - 1 ;

	f[m] = 0 ;

	for (int s = m - 1 ; s >= 0 ; s -- ) {

		double sum = 0 ;

		for (int j = 0 ; j < n ; j ++ ) {

			if ( (s & (1 << j)) == 0 ) {

				sum += P[j+1] ;

				int _s = s | (1 << j) ;

				f[s] += P[j+1] * f[_s] ;

			}

		}

		f[s] ++ ;

		f[s] = f[s] / sum ;

	}

	printf( "%lld\n%.3lf\n" , ans , f[0] ) ;

	return 0 ;

}