Atcoder 刷题记录

· · 休闲·娱乐

Atcoder 刷题记录

刷着玩玩

ARC173A

就先把最近搞的先扔上来吧

考虑一个数位 dp，dfs (int nw, int la, bool st, bool z) 表示当前第 nw 位，上一位是 la，是否顶上界是否是前导零

然后二分一下就可以了

ABC344F

一眼 dp

设状态 dp_{i, j} 表示走到 i, j 的最少步数，然后还要存一下余额

这里转移 i, j 的时候枚举一个点刷钱，先计算出这个点到 i, j 的最少花费，然后记录最少的刷钱次数，再计算出步数和余额，如果步数更少，或者步数一样余额更多就是更优的，更新

初始状态是 dp_{i, j} 存的步数是 \infty ，每次找刷钱的点的时候，要重新赋值最短距离并重新计算

所以综上，复杂度是 O(n^4)