読者です 読者をやめる 読者になる 読者になる

Codeforces Croc Champ 2012 - Final D. T-shirt

重量mのTシャツをk枚以上持ってる期待値
それをすべての{m, k}について計算し、大きいものからn個とっていけばいいです。
普通にDPすると案の定TLEなので、僕は必要となる{m, k}の組がせいぜい2n個であることに注目し、遅延評価しました。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>

using namespace std;

typedef long long ll;

const int MAX_N = 3010;
const int MAX_M = 310;

double dp[MAX_N*2+10][MAX_N+1];
bool dpused[MAX_N*2+10][MAX_N+1] = {};
int dpmap[MAX_N+1][MAX_M];
int dpcount = 0;
int n, m;
int data[MAX_N][MAX_M];

double solve(int n, int c, int m) {
    if (n == 0) return 1.0;
    if (c == 0) return 0.0;
    if (dpmap[n][m] == -1) {
        dpmap[n][m] = dpcount;
        dpcount++;
    }
    int add = dpmap[n][m];
    if (dpused[add][c]) return dp[dpmap[n][m]][c];
    dpused[add][c] = true;
    dp[add][c] = (solve(n-1, c-1, m) * data[c-1][m]
                + solve(n, c-1, m) * (1000 - data[c-1][m]));
    dp[add][c] /= 1000;
    return dp[add][c];
}

int main(int argc, char *argv[]) {
    fill((int *)dpmap, (int *)dpmap + (MAX_N+1)*MAX_M, -1);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &(data[i][j]));
        }
    }
    int res[MAX_M] = {};
    fill(res, res + MAX_M, 1);
    double result = 0;
    for (int i = 0; i < n; i++) {
        int maxm = 0;
        double maxp = -1;
        for (int j = 0; j < m; j++) {
            double p = solve(res[j], n, j);
            if (p > maxp) {
                maxp = p;
                maxm = j;
            }
        }
        result += maxp;
        res[maxm]++;
    }
    printf("%.13lf\n", result);
    return 0;
}