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

Автор Baba, 10 лет назад, По-английски

I've been trying to solve this problem on DP and though the logic seems clear , there's some mistake in the code which i am unable to track down. I am getting a WA on test 36.

My code

Kindly help me track down the problem Thanks

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

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

prev[v] = w; // there is a mistake.
1 3 1
1 4 1
1 2 2
2 5 3 //edge 4
4 5 3 //edge 5
order of edges 4 and 5 matters.

int prevW = -1;
int prevPos = 0;
for(int i = 0; i < m; ++i)
{
    int x = edges[i].x;
    int y = edges[i].y;
    int w = edges[i].w;
    if (prevW != w)
    {
        for (int j = prevPos; j < i; ++j)
            d0[edges[j].y] = d1[edges[j].y];
        prevW = w;
        prevPos = i;
    }
    if (d1[y] < d0[x] + 1)
        d1[y] = d0[x] + 1;
}