【NOI模拟赛】刮痧（动态规划）

题面

　数据范围

对于 100% 的数据，$1\le n\le 15,1\le m\le 100,1\le a_i\le 100,\sum a_i\ge m$，不用担心精度问题。

题解

和「通用测评号」是一样的套路。

对操作序列进行考虑，假设一共有 $k$ 个怪物被击败，死亡时间从小到大排序是 $t_1,t_2,...,t_k$ ，那么在 $(t_i,t_{i+1}]$ 之间的序列元素，概率权值都是 $\frac{1}{n-i}$ 。一种概率权值序列的贡献，等于概率权值乘积乘上对应该权值序列的操作序列方案数。

具体地，我们可以把被击败的怪物和不会被击败的怪物分开考虑，当我们确定被击败的怪物集合 $S$ 以及被击败的怪物在操作序列中的排布，即同时确定了概率权值序列时，剩下的就是不会被击败的怪物在固定的位置上随便放的方案数了。

令 $g[i][S]$ 表示不会被击败的怪物集合为 $S$ ，总损失血量为 $i$ 的方案数，这个可以背包转移，处理时间复杂度 $O(2^n{m}^2)$ ，常数 <1。

接下来确定概率权值序列，令 $f[i][S]$ 表示当前已经刮了 $i$ ，已被击败怪物集合为 $S$ ，所有方案的权值积总和。我们往后填操作序列，挨个确定 $t_i$ 以及被击败的怪物 $j$，确定时再往操作序列里放 $a_j$ 个 $j$ 。令 $sum[S]={\sum }_{i\in S}{a}_i$，转移如下：

• 当前位置不属于 $\{t\}$ ：$f[i+1][S]\leftarrow f[i][S]\cdot \frac{1}{n-|S|}$
• 当前位置属于 $\{t\}$ ：$f[i+1][S\cup j]\leftarrow f[i][S]\cdot \left(\genfrac{}{}{0ex}{}{i-sum[S]}{a_j-1}\right)\cdot \frac{1}{n-|S|}$

时间复杂度 $O(2^{n}nm)$ 。

答案为 ${\sum }_{S}f[m][S]\cdot g[m-sum[S]][\overline{S}]\cdot |S|$

CODE

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<random>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define MAXN 105
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
    
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
    
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {
    if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {
    x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {
    if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
    
	if(!x) {
    putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {
    putnum(x);putchar(c);}

int n,m,s,o,k;
int a[MAXN],id[1<<15|5],sm[1<<15|5],ct[1<<15|5];
DB g[MAXN][1<<15|5];
DB f[MAXN][1<<15|5];
DB C[MAXN][MAXN];
int main() {
    
	freopen("scraping.in","r",stdin);
	freopen("scraping.out","w",stdout);
	n = read(); m = read();
	for(int i = 1;i <= n;i ++) {
    
		a[i] = read();
	}
	C[0][0] = 1;
	for(int i = 1;i <= m;i ++) {
    
		C[i][0] = C[i][i] = 1;
		for(int j = 1;j < i;j ++) {
    
			C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
	}
	int tp = (1<<n)-1;
	for(int i = 1;i <= n;i ++) id[1<<(i-1)] = i;
	for(int i = 1;i <= tp;i ++) {
    
		sm[i] = sm[i^lowbit(i)] + a[id[lowbit(i)]];
		ct[i] = ct[i^lowbit(i)] + 1;
	}
	for(int i = 0;i <= tp;i ++) g[0][i] = 1;
	for(int i = 1;i <= m;i ++) {
    
		for(int j = 1;j <= tp;j ++) {
    
			g[i][j] = g[i][j^lowbit(j)];
			int d = id[lowbit(j)],jj = j^lowbit(j);
			for(int k = 1;k <= i && k < a[d];k ++) {
    
				g[i][j] += g[i-k][jj] * C[i][k];
			}
		}
	}
	f[0][0] = 1;
	for(int i = 0;i < m;i ++) {
    
		for(int j = 0;j < tp;j ++) {
    
			if(sm[j] > i) continue;
			f[i+1][j] += f[i][j]/ct[j^tp];
			for(int k = 1;k <= n;k ++) {
    
				if(!(j & (1<<(k-1)))) {
    
					if(sm[j]+a[k] <= i+1) f[i+1][j|(1<<(k-1))] += f[i][j]*C[i-sm[j]][a[k]-1]/ct[j^tp];
				}
			}
		}
	}
	DB as = 0;
	for(int i = 1;i <= tp;i ++) {
    
		if(sm[i] <= m) as += f[m][i] * g[m-sm[i]][i^tp] * ct[i];
	}
	as = floor(as*100000.0 + 0.5) * 1e-5;
	printf("%.5f\n",as);
	return 0;
}