pstopia Notes for Problem Solving Contest

[Medium] FoxAverageSequence

Topcoder SRM 501 Div1

Problem

DP D[i][S][a][0,1] = 1번째부터 i번째까지 수를 정했고, 그 수들의 합이 S, i번째 수가 a 일 때, 조건을 만족하는 경우의 수 맨 끝이 0일 땐 (i-1번째 수) <= a, 맨 끝이 1일 땐 (i-1번째 수) > a 로 경우를 나눈다.
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1000000007;
int d[2][1601][41][2];
class FoxAverageSequence {
public:
int theCount(vector<int> seq) {
vector<int> st(seq.size(), 0), ed(seq.size(), 40);
for (int i = 0; i < (int)seq.size(); ++i) {
if (seq[i] != -1) {
st[i] = ed[i] = seq[i];
}
}
int ans = 0;
for (int i = 0; i < seq.size(); ++i) {
int p = i % 2;
memset(d[p], 0, sizeof(d[p]));
if (i == 0) {
for (int s = st[i]; s <= ed[i]; ++s) {
d[p][s][s][0] = 1;
if (i + 1 == seq.size()) {
ans = (ans + d[p][s][s][0]) % MOD;
}
}
continue;
}
for (int s = 0; s <= (i + 1) * 40; ++s) {
for (int a = st[i]; a <= ed[i] && (i + 1) * a <= s; ++a) {
for (int b = st[i - 1]; b <= ed[i - 1] && a + b <= s; ++b) {
if (b > a) {
d[p][s][a][1] = (d[p][s][a][1] + d[1 - p][s - a][b][0]) % MOD;
}
else {
d[p][s][a][0] = (d[p][s][a][0] + d[1 - p][s - a][b][0]) % MOD;
d[p][s][a][0] = (d[p][s][a][0] + d[1 - p][s - a][b][1]) % MOD;
}
}
if (i + 1 == seq.size()) {
ans = (ans + d[p][s][a][0]) % MOD;
ans = (ans + d[p][s][a][1]) % MOD;
}
}
}
}
return ans;
}
};