AtCoder 板刷记录

话说为啥这些场都没有 G 题的说

[ABC200F] Minflip Summation

显然的策略是把全部都是一个数的段变成全不都是另一个数，然后考虑进行 dp

设一个 dp[i][0/1][0/1] 表示一下前 i 个字符中奇偶性为 j 填的数是 k 时 j 的总和

然后直接做就行了，需要矩阵快速幂加速一下

[ABC201F] Insertion Sort

考虑进行 dp 维护，很显然一个人只会有移动一次，因为反复横跳是没有意义的，而且并不优

那么我们就可以设出一个 f_i 表示对于对于不超过 i 的人（i \belong S）的代价最小值

我们如果确定了一个顺序 {S_i} 我们就可以知道，我们只需要进行分类讨论，如果 A_i < S_i 就直接取一个 min(a_i,b_i)

如果 A_i > S_i 我们就取一个 min(a_i,c_i) 就行

我们需要最小化代价和，可以发现没有后效性，考虑 dp 即可

转移方程是 dp[i] = min ( \sum_{j=1}^{i-1} min(A_j,B_j), min_{j<i}(dp[j] + \sum _{k=j+1}^{i-1} A_k))

最后的答案是 min(dp[j] + \sum_{j=i+1}^n (A_i+C_i))

复杂度 O(n^2)，发现似乎不是很优秀，那么考虑用线段树优化到 O(n log n)

[ABC203F] Weed

容易发现这道题是一个 dp,用 dp[i][j] 表示进行 j 次操作拔掉前 i 棵的草

转移方程是 dp[i][j]=min{dp[i−1][j]+1,dp[i′][j]}

预处理出 i' 然后暴力转移即可，这样就解决了

[ABC204F] Hanjo 2

还在写