SRM 501 div1 med:FoxAverageSequence

問題

TopCoder Statistics - Problem Statement

解法

dp[cur][sum][before][de] := (今cur番目の数を見ていて,cur未満の数での総和はsumになっていて,curの直前の数はbeforeで,de個strictに数が減少している時の条件を満たす場合の数)
として,適切に漸化式を立てる。
dpの型をllで宣言するとメモリ制限をオーバーするっぽいので注意。
また計算量的に厳しいと思われるが適当に枝刈りしているししてなくてもなんだかんだO(10^8)なので計算の早いtopcoderサーバなら大丈夫。
以下ソースコード

const ll MOD = 1e9+7;
int dp[41][41*41][41][2];

class FoxAverageSequence {
public:
    int theCount(vector <int> seq) {
        memset(dp, -1, sizeof(dp));
        dp[0][0][0][0] = 1;
        int n = seq.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 40*40; j++) {
                for (int k = 0; k <= 40; k++) {
                    for (int l = 0; l < 2; l++) {
                        if (dp[i][j][k][l] == -1) continue;
                        if (seq[i] != -1) {
                            int de = l;
                            if (k > seq[i]) de++;
                            else de = 0;
                            if (de >= 2) continue;
                            if (j < seq[i]*i) continue;
                            int sum = j+seq[i];
                            if (dp[i+1][sum][seq[i]][de] == -1) dp[i+1][sum][seq[i]][de] = 0;
                            (dp[i+1][sum][seq[i]][de] += dp[i][j][k][l]) %= MOD;
                        } else {
                            for (int m = 0; m <= 40; m++) {
                                int de = l;
                                if (k > m) de++;
                                else de = 0;
                                if (de >= 2) continue;
                                if (j < m*i) break;
                                int sum = j+m;
                                if (dp[i+1][sum][m][de] == -1) dp[i+1][sum][m][de] = 0;
                                (dp[i+1][sum][m][de] += dp[i][j][k][l]) %= MOD;
                            }
                        }
                    }
                }
            }
        }
        ll ans = 0;
        for (int i = 0; i < 41*41; i++) {
            for (int j = 0; j < 41; j++) {
                for (int k = 0; k < 2; k++) {
                    if (dp[n][i][j][k] == -1) continue;
                    (ans += dp[n][i][j][k]) %= MOD;
                }
            }
        }
        return ans;
    }
};