三维数组的看过来

P1855 榨取kkksc03

@[xiaoshulin](/user/396731) 为什么要从0开始,不能在循环中写 j >= c1[i] 和 k >= c2[i]
by zly1783598949 @ 2021-09-27 20:52:38


从$0$开始循环是为了保证状态的合法性,比如kkk的钱不够或者时间不够,这都是合法的,就有 $dp[i][j][k]=dp[i-1][j][k]$ 这代表我们不能选择这件物品。如果直接从$c1[i]$ 和 $c2[i]$ 开始循环就会忽略这些状态。 比如 对于 ``` 3 8 5 5 3 10 6 2 2 ``` 如果不从$0$开始循环,那么 $dp[2][i][j]$都会是 $0$因为 $10 > 8, 6 > 5$那么实际上,对于$dp[2][8][5]$等等状态来说,实际上应该等于1,因为可以买到前一个物品。所以错误的程序跑出了$1$,实际上答案是$2$。 为何压缩的二维数组不需要这样? 因为对于二维数组来说,它少了一个维度,它的所有数据都是已经填好的,还是拿上一个例子,因为在第一次处理$i==1$的时候,$dp[8][5]=1$相当于前一个愿望可以最多实现一个,但是对于第二个愿望,没有办法实现,但是在数组里面,$dp[8][5]==1$这就相当于三维数组的时候$dp[2][8][5]=1$,这就保留了前一个阶段的数据,所以这就是为什么压缩的二维数组不需要从0开始。
by xiaoshulin @ 2021-09-28 09:33:46


@[zly1783598949](/user/394113)
by xiaoshulin @ 2021-09-28 13:13:35


@[xiaoshulin](/user/396731) 谢谢
by zly1783598949 @ 2021-09-29 21:15:42


@[xiaoshulin](/user/396731) (为什么)[https://www.luogu.com.cn/record/71620971]
by 徐崇瑜 @ 2022-03-17 20:23:36


@[徐崇瑜](/user/490879) ???
by xiaoshulin @ 2022-03-18 14:19:18


TLQTJ
by JuRuoOIer @ 2022-07-18 14:09:38


|