OJ Board

dp?

yes, it's DP

time complexity is about o(k * n^2)


Hint :

think when there is no rule that :
You can step on at most k negative integers from source to destination.


then you'll get DP algorithm,

and add this rule to your algorithm.

it will be not difficult.

ac now
Thank you

Crazy autologin
Previous post is mine.

Anonymous wrote:

wook wrote:yes, it's DP

time complexity is about o(k * n^2)

Are you sure about o(k * n^2) ?

My algo takes o(k * n^3). And work fast enough.

My time complexity is O(kn^2), too. And the memory complexity is O(kn).

Thx, I optimized my algo. Now it's O(k * n^2) too.

However running time didn't improved much.

kp wrote:Thx, I optimized my algo. Now it's O(k * n^2) too.

However running time didn't improved much.

It would have been more significiant if n would be much bigger than 75.

Can someone post some example cases? Thanks!

Larry wrote:Can someone post some example cases? Thanks!

I'm lazy to generate any inputs , but if you post some here I can generate the correct answers for you.

hi,
i cannot make a way to use DP in this problem. if you anyone describe how to implement DP here, i will be greatly helped. btw, can this problem be solved within time limit using dfs?
thanks in advance...

ayon wrote:hi,
i cannot make a way to use DP in this problem. if you anyone describe how to implement DP here, i will be greatly helped. btw, can this problem be solved within time limit using dfs?
thanks in advance...

I used following DP-algorithm:
In cell t[i,j,g] save the maximum sum of integers of the path to cell(i,j), g is a count negative integer in the sum.
1.) As we start at cell (1,1), in all cells of first row we can arrive from left only. So, t[1,i,g] = t[1,i-1,g]+m[1,i] if m[1,i] >= 0 else t[1,i,g+1] = t[1,i-1,g]+m[1,i].
2.) Then for all row from 2 to n do:
- move down from row (i-1) to row i
if m[i,j] >= 0 then t[i,j,g] = t[i-1,j,g]+m[i,j]
else t[i,j,g] = t[i-1,j,g-1]+m[i,j]
- buf1[j,g] = buf2[j,g] = t[i,j,g]
- move from cell(i,1) to cell (i,n) try to maximize the result in buf1:
if (m[i,j] >= 0) then buf1[j,g] = max(buf1[j,g],buf1[j-1,g]+m[i,j]) else buf1[j,g] = max(buf1[j,g],buf1[j-1,g-1]+m[i,j])
- also move from cell(i,n) to cell (1,n) correct buf2
- t[i,j,g] = max(t[i,j,g],buf1[j,g],buf2[j,g]);
3.) the maximum sum of integers of the path is max(t[n,n,g]) where 0<=g<=k.

thank you very much Andrey, now i understand clearly how to use DP here. your explaination is very clear and fine. thanks again for the help

Someone pls send some critical data, i m getting WA again and again. i use DP.

Thx in Advace.

L I M O N

L I M O N wrote:Someone pls send some critical data, i m getting WA again and again. i use DP.

Thx in Advace.

L I M O N

Try this input: Output:

my outputs :

Case 1: 1
Case 2: impossible
Case 3: -1
Case 4: 9
Case 5: 13
Case 6: 14
Case 7: -5
Case 8: impossible
Case 9: 280

but Same result, WA.
do u use "long long" data type ? i also use this type.

pls send more data

L I M O N