02.03 ARC 119C

连续两个数字同时+1/-1

统计子数组和为K的数量的算法

交错和相等的子数组就是答案 => 奇数乘以+1,偶数乘以-1,得到的子数组和恰好为0 =>转化成子数组和为0的问题 => 容易解决

其他记录:

ABC 288D

前缀类型套路+思维题

给定一组需要买的物品B1,B2,…BK

如何安排一个最好的顺序去买这K个物品，花费最少

当你买$B_i$时, 如果之前你已经买了$B_1,B_2,…,B_{i-1}$中的$x$件物品
那么第$B_i$实际上对应第$B_i - x$个没有被售出的商品

由于$x$属于$0$到$i - 1$ 所以花费至少是$A_{B_i} + cost(B_i, i-1)$

$cost(i,j) = min{C_{i-j},…, C_{i-2},C_{i-1}, C_{i} }$

买所有的物品花费总和至少需要 $\sum_{i=1}^k (A_{B_i} + cost(B_i, i-1))$

证明这个下界是可以取到的

当你想要买物品$i$的时候, 取决于之前买了多少物品,记作$j$件
那么买的代价就是$A_i + cost(i,j)$

所以可以列出这个状态

$dp[i][j]$表示前$i$个物品中, 买了$j$个物品的最小代价

$dp[i+1][j+1] <- min{dp[i+1][j+1], dp[i][j]+cost(i+1,j) }$
$dp[i+1][j] <- min{dp[i+1][j], dp[i][j]}$

通过预处理$cost(i,j)$我们可以通过一个$n^2$的dp解决问题

给你一个数字组成的字符串X,长度为N, 保证没有0

考虑一个${1,2,3,..,N-1}$的一个子集$S$

定义$f(S)$等于断开$S$中对应位置后

剩余数字字符串得到的乘积

问这个和是多少?

例如

234

2 | 34
2 | 3 | 4
23 | 4
234

容易得到的一个dp方法:
$dp_j = \sum_{i=0}^{j-1} dp_i * X[i+1:j], \forall i < j$

然后可以发现喜提TLE(太慢了 N2)

如何优化这个dp的转移?
$dp_j = dp$

注意到$X[i:j] = 10X[i:j-1] + X[j]$

$$
dp_j = \sum_{i=0}^{j-1} dp_i * X[i+1:j]
= \sum_{i=0}^{j-1} dp_i * (10X[i+1:j-1] + X[j:j])
= 10dp_{j-1} + X[j:j] \sum_{i=0}^{j-1} dp_i
$$

可以发现变成了一个递推+前缀和的形式于是就可以简化计算到$O(N)$