Submission: https://atcoder.jp/contests/abc334/submissions/48804245

解法是一个普通 dp，对要枚举的礼物个数加了个单调性优化，自己算的时间复杂度是 $O(n \times \min(n, k))$，感觉是卡过的。

所以，这种做法的时间复杂度是否正确？如果正确，是否可证？