11/7
08:27
OI

CF183D T-shirt [期望DP][贪心]

CF183D T-shirt

考虑一个暴力一些的DP.钦定当前正在考虑第x件衣服,那么设计f_{i,j},表示选i个,送j个的期望

f_{i,j} = f_{i-1,j-1}p_{i,x} + f_{i-1,j}(1-p_{i,x})

然后考虑计算对答案贡献的期望

E_i = \sum_{j=0}^i jf_{n,j} + \sum_{j=i+1}^n if_{n,j}

有了E,可以背包求解.

考虑对E作差

delta=E_{i+1} – E_i = \sum_{j=i+1}^n f_{n,j} = 1-\sum_{j=0}^i f_{n,j}

显然f递增,即差越来越小.所以,可以考虑求出所有x,选0个的delta,贪心选取最优x,然后更新delta.

#include <bits/stdc++.h>

const int N = 3010, M = 310;

int n, m; double p[N][M];
double f[M][N], g[N], delta[M];
double ans;

void calc(int x, int op = 0) {
  for (int i = 0; i <= n; ++i)
    g[i] = f[x][i];
  f[x][0] = op;
  for (int i = 1; i <= n; ++i)
    f[x][i] = g[i - 1] * p[i][x] + f[x][i - 1] * (1 - p[i][x]);
  delta[x] -= f[x][n];
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      int x; scanf("%d", &x);
      p[i][j] = (double)x / 1000;
    }

  for (int i = 1; i <= m; ++i) {
    delta[i] = 1;
    calc(i, 1);
  }

  for (int i = 1; i <= n; ++i) {
    int pos = 0;
    for (int j = 1; j <= m; ++j)
      if (delta[j] > delta[pos])
        pos = j;
    ans += delta[pos];
    calc(pos);
  }
  printf("%.12lf\n", ans);
  return 0;
}