Мое решение (ниже) - это ДП, в котором для каждой клумбы перебираются все предыдующие клумбы, из которых можно прийдти в текущую. Для каждой такой пары (текущая <-> какая-то сзади) перебираются все возможные варианты деревьев. Итого, решение O(M*M*N*N). Но, увы, на каком-то из непервых тестов получаю WA. То есть решение вроде бы верно, но не совсем ;-).
Подскажите проблему, кто видит.
int M;
is >> M;
vector<int> w(M), e(M);
for (int i = 0; i < M; ++i)
is >> w[i] >> e[i];
int N;
is >> N;
vector<int> p(N);
for (int i = 0; i < N; ++i)
is >> p[i];
vector<vector<int> > dp(M, vector<int>(N, 0));
for (int i = 0; i < M; ++i)
dp[i][0] = 1;
for (int i = 1; i < N; ++i) {
for (int j = 0; j < M; ++j) {
for (int i0 = 0; i0 < i; ++i0) {
for (int j0 = 0; j0 < M; ++j0) {
if (p[i0] + e[j0] <= p[i] && p[i] - w[j] >= p[i0])
dp[j][i] = max(dp[j][i], dp[j0][i0] + 1);
}
}
}
}
int ans = 0;
for (int i = 0; i < M; ++i)
ans = max(ans, dp[i][N - 1]);
os << ans << endl;
}
Comments (0)
