()
| 68 | } |
| 69 | |
| 70 | public static int compute() { |
| 71 | // 注意这里第二层for循环，j一定是从k~0的枚举 |
| 72 | // 课上进行了重点图解，防止同一个i产生的记录之间相互影响 |
| 73 | int v, dp; |
| 74 | for (int i = 1; i <= n; i++) { |
| 75 | for (int j = k; j >= 0; j--) { |
| 76 | v = arr[i] + j; |
| 77 | // 修改次数j，树状数组中对应的下标是j+1 |
| 78 | dp = max(v, j + 1) + 1; |
| 79 | update(v, j + 1, dp); |
| 80 | } |
| 81 | } |
| 82 | // 修改次数k，树状数组中对应的下标是k+1 |
| 83 | return max(MAXH, k + 1); |
| 84 | } |
| 85 | |
| 86 | } |