CF183D T-shirt

本题的第一个转化很关键，也是这种期望题必须要观察到的一个性质，就是每种衣服的的贡献可以单独算。

因为一个人喜欢一种衣服就不会喜欢另一种衣服，也就是说喜欢每一件衣服的概率是独立的，那么这种时候我们就能发现实际上本题的每种衣服的贡献可以单独算。

再做推广就是 相互独立的事件的贡献可以分开算，也即期望的线性性。
记 \(f[i][j][k]\) 表示前 \(i\) 个人有 \(j\) 个人喜欢第 \(k\) 种衣服的概率, \(p[i][k]\) 为第 \(i\) 个人喜欢第 \(k\) 种衣服的概率。

设 \(g[i][k]\) 表示准备了 \(i\) 件第 \(k\) 种衣服，送出衣服件数的期望

对 \(g[i][k]\) 做一遍背包就可以做到 \(O(n^2m)\) 的复杂度

然后考虑进行一些优化。
有一个很关键的性质 \(\Sigma_{j=1}^nf[n][j][k]=1\) 那么

所以 \(g[i + 1][k] – g[i][k]\) 单调递减且永远 \(\geq 0\) 那问题就简单了，只需要进行一遍贪心每次选择增长最多的 \(g[i + 1][k]\) 对其 \(+1\) 即可。
现在问题就在于如何计算增量。
我们不需要改写 \(f\) 数组的状态含义只需要少记一维也即将 \(f[i][j][k]\) 变为 \(f[i][k]\) \(j\) 则记为 \(cnt[k]\) 即可，每次增加就转移一下即可。

代码

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
using namespace std;
template <typename T> void read(T &n){ bool f = 1; char ch = getchar(); n = 0; for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 0; for (; isdigit(ch); ch = getchar()) n = (n << 1) + (n << 3) + (ch ^ 48); if (f == 0) n = -n;}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

#define ld long double
const int N = 3e3 + 10, M = 3e2 + 10;
int n, m;
ld last[N + 5], delt[M + 5], dp[M + 5][N + 5], p[N + 5][M + 5];

inline void init() {
	U(i, 1, m) {
		dp[i][0] = 1;
		U(j, 1, n)
			dp[i][j] = dp[i][j - 1] * (1 - p[j][i]);
		delt[i] = 1 - dp[i][n];
	}
}

inline void update(int c) {
	ld g[N] = {};
	memcpy(g, dp[c], sizeof g);
	dp[c][0] = 0;
	U(i, 1, n) {
		dp[c][i] = dp[c][i - 1] * (1 - p[i][c]) + g[i - 1] * p[i][c];
		// cerr << dp[c][i] << " " << g[i - 1] << "\n";
	}
	delt[c] -= dp[c][n];
} 

int main(){
	//FO("");
	read(n), read(m);
	ld ans = 0;
	U(i, 1, n) U(j, 1, m) {
		int x;
		read(x);
		// read(x);
		p[i][j] = x / 1000.0;
		// printf("%.12Lf\n", &p[i][j]);
	}
	init();
	U(i, 1, n) {
		int x = 0;
		U(j, 1, m) 
			if (delt[j] > delt[x]) x = j;
		// cerr << delt[x] << "\n";
		ans += delt[x];
		update(x);
	}
	printf("%.12Lf", ans);
	return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16836015.html