Блог пользователя begoon

Задача "Еловая аллея"
Автор begoon, 14 лет назад, По-русски

Мое решение (ниже) - это ДП, в котором для каждой клумбы перебираются все предыдующие клумбы, из которых можно прийдти в текущую. Для каждой такой пары (текущая <-> какая-то сзади) перебираются все возможные варианты деревьев. Итого, решение O(M*M*N*N). Но, увы, на каком-то из непервых тестов получаю WA. То есть решение вроде бы верно, но не совсем ;-).

Подскажите проблему, кто видит.

void solve(istream& is, ostream& os) {
  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;
}
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
P.P.S. Что-то я невнимательно прочел условие. Я подумал, что ель каждого сорта можно использовать только 1 раз, но тогда она не решается в данных ограничениях. А если можно несколько раз, то очень просто - наплодим отрезков от l до r и найдем максимальное множество непересекающихся отрезков, а эта задача решается классически - сортировка по правой границе и ДП.
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
извиняюсь, похоже, Вы так и делаете.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Пусть N = 2,  M = 1,    w1 = e1 = 30000,   p = {1,2}, Ваше решение по идее даст ответ 0, а должно быть 1
→ Ответить