[ARC127E] Priority Queue


题目描述题目传送门思路正着做比较困难,反着来。假设 {a}\{a\}{a} 是我们最后剩下来的集合。可以发现一个结论:aaa 是一个单调上升序列肯定不劣。这样我们可以从头开始加入数字。每一此 2 操作实际上可以与其之前的 1 操作抵消。所以我们无需考虑二操作。由于我们可以证明 aaa 单调升。可以设

[USACO22DEC] Bribing Friends G


题目描述题目传送门思路有显然的三维 dp。设 fi,j,kf_{i,j,k}fi,j,k​ 表示前 iii 个朋友用了 jjj 个哞尼和 kkk 个冰激凌甜筒能得到的最大价值。那么有:fi,j,k=max⁡w>ci,w×xi>k{fi−1,j,k,fi−1,j−ci+w,k−w×xi+p

[PA2021] Od deski do deski


题目描述题目传送门思路计数题,很容易想到 dp。难点在于状态的设计,显然有一维状态是序列长度,有一维表示合法与否,dp 值表示为方案数,记为 fi,0/1f_{i,{0/1}}fi,0/1​。这样是没有办法转移的,因为我们接下来要填什么与之前填的数字有关,考虑加维。发现对于一个合法序列 SSS,假设

CF1616D Keep the Average High


题目描述题目传送门给定一个长 nnn 的数列 aaa,再给定一个 xxx。你需要选中其中一些数,使得对于所有连续的被选中的长度至少为 222 的子串 $[l,r] $ 满足:∑i=lrai≥(r−l+1)×x\sum_{i=l}^ra_i\ge (r-l+1)\times xi=l∑r​ai​≥(r

[CERC2014]The Imp


题目传送门题目传送门思路Lemma. 按照 viv_ivi​ 升序购买一定最优。Proof. 设先后购买的为 (v1,c1),(v2,c2)(v_1,c_1),(v_2,c_2)(v1​,c1​),(v2​,c2​) 其中 v1≤v2v_1 \le v2v1​≤v2。此时的答案为 min⁡(v1−c

[POI2015] LAS


题目描述题目传送门思路这题黑是恶意评分吧考虑 dp,先想状态怎么设。很容易想到的第一种 dp,假设 $dp_{i,j}$($j \in \{1,2\}$),表示第 $i$ 个人吃了左边($j = 1$)或者 右边($j = 2$)的食物,可是这样似乎没有什么转移关系,所以做不了(~~或者我太菜了不会

CF797E Array Queries


题目描述题目传送门1题目传送门2给定长度为 $n$ 的序列 $a$。$m$ 次询问。每次询问给出 $p,k$。您要不断地执行操作 $p\gets p+a_p+k$,直到 $p>n$ 为止。询问的答案为操作次数。$1\le n,q\le 10^5$,$1\le a_i\le n$。思路Algor