AtCoder Educational DP Contest

· · 个人记录

Educational DP Contest Luogu | AtCoder

A Frog 1

第一遍交 f_2 的处理有问题，WA 了一个点，身败名裂！！

B Frog 2

所幸，没有身败名裂。

C Vacation

非常套路。

D Knapsack 1

震惊，zerc 竟然连背包都不会写了，身败名裂！！

半个小时写背包，半个小时 debug，结果发现没开 long long。

E Knapsack 2

这个思路还是第一回见呢，挺新奇。

然后数组开小了 RE & WA，++，身败名裂！！

F LCS

看了一眼，并没有加强版（（

唯一的不同是需要输出方案，需要根据 f 数组回溯，也是第一回见。

然后复习了一下 O(n) 的解法。

G Longest Path

上来写了个 Dijkstra，后来发现并不需要（写挂了。

直接 topsort 更新 deep 就完了，

H Grid 1

非常套路。

I Coins

概率 DP，好久不做手生了 qwq，也是套路题。

J Sushi

++，期望，不会做（或说期望 DP 还是我讲的嘞，结果我还是不会。

He 完之后发现好简单，，，但就是不会，期望还是要多做嘞。

K Stones

大概就是伪装成博弈论的 dp。

L Deque

NOI 2022 Day1 T1

区间 dp，但是没看出来，好像还挺裸的，不用枚举断点，所以是 O(n^2) 的。

M Candies

前缀和优化。

N Slimes

还是区间 dp。

O Matching

NP 问题，为什么没有想到状压，，，

P Independent Set

树形 dp 板子题，加法乘法傻傻分不清。

Q Flowers

线段树优化转移（直接把 f 优化没了。。

R Walk

很早之前做的了，矩乘板子。

S Digit Sum

数位 dp，看名字大概也是。

T Permutation

U Grouping

V Subtree

W Intervals

Solution

所以是取 min 还是取 max 呢。

X Tower

Solution

贪心 + DP，，。

Y Grid 2

Z Frog 3

Solution