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

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

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
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← 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

→ Ответить
  • »
    »
    10 лет назад, скрыть # ^ |
    ← 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]));
}
    → Ответить