n*******s
发帖数: 482 | 1 People say this is a typical DP problem, fundamental level. | m*****f
发帖数: 1243 | 2 topcoder题目? 不是有别人做的代码可以看吗 | k***e
发帖数: 556 | 3 看到这么长的题目 我一般放弃 都没耐心读完他
【在 m*****f 的大作中提到】
: topcoder题目? 不是有别人做的代码可以看吗
| g*******y
发帖数: 1930 | 4 假设子问题针对第1号到第i号(前i个人)，但是首尾不相连(1号和i号不是邻居)：
需要知道子问题里第i号是否要donate
当做到最后一个人(第n号)的时候，因为最后一个人既跟n-1号人，又跟1号相邻，那么就需要知道子问题里面第1号人是否donate
也就是说，子问题的state需要几个参数：
1个bit来表示第一个人是否donate
1个bit来表示最后一个人是否donate
1个int i来表示从1号到第i号人的子问题
也就是说，用一个数组：
a[2][2][n]来保存每个子问题的解。
定义好子问题后，写出状态转移方程，然后一直算到倒数第二个人结束。第n个人单独处理一下 | n*******s
发帖数: 482 | 5 just wake up and consider it again:
Trying to solve it in this way:
original problem: a1, a2, ....ai, ...an-1, an
subproblem : a1, a2, ... ai
Define array: L[2][n]
L[0][i] --> the max donation where the ith neighbor won't donate
L[1][i] -->the max donation where the ith neighbor will donate
Recursive relation:
L[0][i+1] = max {L[0][i], L[1][i]}
L[1][i+1] = L[0][i] + a[i]
However, during this extension, we don't consider the head/tail collision, but this will be problem. So at the final st | g*******y
发帖数: 1930 | 6 how about
note: inf = infinity
numbers: inf, inf/2,.....10,inf*0.75
all your L[0][] L[1][] will select the first number:"inf"
when it comes to the last number "inf*0.75"：
which number to sacrifice？
obviously the answer should abandon the first "inf", but if you abandon the first number, your L[][] result will become useless
this is exactly what I meant in my post:
You don't define a "state"(i.e,subproblem) well enough if you don't specify whether the first number is chosen or not.
【在 n*******s 的大作中提到】
: just wake up and consider it again:
: Trying to solve it in this way:
: original problem: a1, a2, ....ai, ...an-1, an
: subproblem : a1, a2, ... ai
: Define array: L[2][n]
: L[0][i] --> the max donation where the ith neighbor won't donate
: L[1][i] -->the max donation where the ith neighbor will donate
: Recursive relation:
: L[0][i+1] = max {L[0][i], L[1][i]}
: L[1][i+1] = L[0][i] + a[i]
| n*******s
发帖数: 482 | 7 l's inital value would be
L[0][0] = 0
L[1][0] = a[0]
since, L[0][i] means the possible max if the ith does not donate
L[1][i] means the possible max if the ith does donate
Here is the code:
int a[] = { 94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237
, 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45,
435, 7, 36, 57, 86, 81, 72 };
int size = sizeof(a)/sizeof(int);
int l[2][size];
int m[size];
int type=0;
int i =0, j=0, max=0;
m | g*******y
发帖数: 1930 | 8 have you tried my test case?
inf, inf*0.5, ...(normal numbers),inf*0.7
you can use 9999999 as inf.
237
【在 n*******s 的大作中提到】
: l's inital value would be
: L[0][0] = 0
: L[1][0] = a[0]
: since, L[0][i] means the possible max if the ith does not donate
: L[1][i] means the possible max if the ith does donate
: Here is the code:
: int a[] = { 94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237
: , 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45,
: 435, 7, 36, 57, 86, 81, 72 };
: int size = sizeof(a)/sizeof(int);
|
|
