DP -> Slope Trick

Convex piecewise-linear DP over one integer coordinate maintained by hinge additions and bounded argmin shifts.

• Topic slug: dp/slope-trick
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 4
• Curated external problems: 4

Microtopics

• convex-piecewise-linear-dp
• two-heaps
• hinge-penalties
• argmin-interval
• shift-min
• movement-relaxation

Learning Sources

Source	Type
AtCoder ABC217 H Editorial	Reference
AtCoder ABC406 G Editorial	Reference
AtCoder ARC163 F Editorial	Reference

Practice Sources

Source	Type
AtCoder ABC127 F Absolute Minima	Practice
AtCoder ABC217 H Snuketoon	Practice
AtCoder ABC406 G Travelling Salesman Problem	Practice

Repo Companion Material

Material	Type
Slope Trick hot sheet	quick reference
Snuketoon note	flagship note
Template Library exact starter route	starter route
Convex Hull Trick / Li Chao Tree tutorial	compare point

Curated External Problems

Warm-Up

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Absolute Minima	AtCoder	Hard	-	Online Queries; Median Structure	Absolute Value Cost; Convex Minimizers	Absolute Value Updates; Median Maintenance; Convex Function	The clean warm-up where the same convex-function family appears without movement-style shift_min, so a lighter same-family route becomes visible.

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Snuketoon	AtCoder	Hard	-	Convex DP; Data-Structure-Heavy	Convex Function State; One-Sided Hinges; Lazy Shifts	One-Sided Penalties; Shift Min; Convex DP	The cleanest flagship where time gaps become bounded argmin shifts and each event adds one one-sided hinge penalty.

Stretch

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Travelling Salesman Problem	AtCoder	Hard	-	Convex DP; Follow-Up	Slope Trick; Absolute Distance DP	Absolute Distance; Shift Min; Follow-Up	A strong follow-up where the same slope-trick machinery survives a different story skin and both movement and meeting costs shape the convex state.

Challenge

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Many Increasing Problems	AtCoder	Hard	-	Convex DP; Theory-Heavy	Slope Trick; Sequence DP	Monotone Sequence DP; Convex DP; Advanced	The advanced follow-up where the slope-trick view still applies, but the problem is no longer a direct event-by-event coordinate process.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
SNUKETOON	Snuketoon	primary	hard	-	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py