OJ Board

in

4 3 10
1000 1 2
1000 3
1000 1
5000 1 2 3 4
50000 3
50000 4
50000 3 4
50000 1
50000 1
50000 2
50000 1
50000 2
50000 1
8 4 20
1000 1
1000 2
1000 3
1000 2
10000 1
20000 2
40000 3 4
50000 1 2
50000 1 4
50000 1
50000 1 3 4
50000 1 2 3 4
50000 1 3 4
50000 1 2 3 4
50000 1 3 4
50000 1 5 7 3 4
50000 1 2 ...

Out of my curiosity what is the idea behind using memoizetion?, I used dynamic programming and my solution is very similar with the classic 0-1 knapsack problem, the only difference is that I have an array of subjects instead of the weight.

Cheers,
R.

Could someone tell me if any of my test cases is wrong ?, is there any tricky test case ?

Regards,
R.

2
2
11
01
4
3
110
101
111
011
1
1
1
1
1
0
3
4
1111
1001
1001
4
4
1111
1111
1001
1001
3
3
111
111
111
4
4
1111
1111
1111
1111
5
5
11111
11111
11111
11111
11111
3
3
111
101
111
6
6
111111
100001 ...

The formula is 1/2 * (m!)/((m/2)!*(m/2)!),
http://www.cs.brandeis.edu/~ira/papers/superballot.pdf

use dynamic programming and store the max value per step, the algo to find the max is:

int findMax(int c, int s, int e, int t, int step) {

if (step == t) {
for (i = 0; i < e; i++)
Max(cost[s][endcity - 1])

}
else
for (j = 0; j < c; j++) {
Max(cost[s][j]+ findMax(c, j, e, t, step + 1 ...