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

How to solve SPOJ CRICKDP
Автор gautam94, история, 9 лет назад, По-английски

Problem: http://www.spoj.com/problems/CRICKDP/

I tried doing it by finding the minimum removal cost for each score in and then using this to calculate the maximum total score by DP, but this is too slow. Any other ideas will be appreciated. Thanks.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

do not understand why answer for second test case is -6. it should be -5. initial ratings are "-1 -2 -3 -4 -5"
bribe first judge "1 3 3" and remove all ratings between 1 and 3 — "(-1 -2 -3) -4 -5"
bribe second judge "3 4 4" and remove all ratings between 3 and 4 — "(-1 -2 [-3) -4] -5" there will be only one rating -5. UPD: Understand. The ith judge demanded Ci amount of money for removing each match

→ Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

    you can find minimal removal cost in N + M log M.

    const int K = 510
const int N = 10100
vector<int> add[N];
vector<int> del[N];
multiset<int> m;
...
for (int i = 0; i < m; ++i)
{
   cin >> L >> R >> C;
   add[L].push_back(C);
   del[L].push_back(C);
}

m.insert(K);
for (int i = 1; i <= N; ++i)
{
   for (int j = 0; j < add[i].size(); ++j)
       m.insert(add[i][j]);
   minCost[i] = *m.begin();
   for (int j = 0; j < del[i].size(); ++j)
       m.erase(m.find(del[i][j]));
}
    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think you meant del[r].push_back(c) on line 11 instead of del[l].push_back(c) and the scores which don't lie inside any valid range can not be removed, so it should be m.insert(k+1) on line 14. I got AC with this code http://ideone.com/EJBqIN Thanks for helping.

      → Ответить