\(\textup{股票交易}\)
设 \(dp_{i,j}\) 表示第 \(i\) 天有 \(j\) 股的最多钱数。
则 \(dp_{i,j} = \max \left\{\begin{matrix} dp_{i-1, j}\\ dp_{i-w-1, k} - ap_i\ *\ (j - k) ,\ (j - sa_i \le k < j)\\ dp_{i-w-1, k} + bp_i\ *\ (k - j) ,\ (j < k \le j + sa_i) \end{matrix}\right. \)
将中间的柿子转换一下：
\[\begin{aligned} dp_{i,j} &= \max \{dp_{i-w-1, k} - ap_i\ *\ (j - k) ,\ (j - sa_i \le k < j)\} \\ &= \max \{dp_{i-w-1, k} - ap_i\ *\ j + ap_i\ *\ k ,\ (j - sa_i \le k < j)\}\\ &= \max \{dp_{i-w-1, k} + ap_i\ *\ k ,\ (j - sa_i \le k < j)\} - ap_i\ *\ j \end{aligned} \]发现可以单调队列优化，时间复杂度为 \(\mathcal{O}(\mathcal{n}^2)\)
int l = 1, r = 0;
for (int j = 0; j <= maxp; j ++){
while (l <= r && q[l] < j - as)
l ++;
while (l <= r && dp[i - w - 1][q[r]] + q[r] * ap <= dp[i - w - 1][j] + j * ap)
r --;
q[++ r] = j;
if (l <= r)
dp[i][j] = max(dp[i][j], dp[i - w - 1][q[l]] + q[l] * ap - j * ap);
}
l = 1 , r = 0;
for (int j = maxp; j >= 0; j --){
while (l <= r && q[l] > j + bs)
l ++;
while (l <= r && dp[i - w - 1][q[r]] + q[r] * bp <= dp[i - w - 1][j] + j * bp)
r --;
q[++ r] = j;
if (l <= r)
dp[i][j] = max(dp[i][j], dp[i - w - 1][q[l]] + q[l] * bp - j * bp);
}
\(\textup{Non-equal Neighbours}\)
喵喵题。
ds 优化 dp。
考虑暴力 dp。
设 \(dp_{i,j}\) 表示第 \(i\) 个数选 \(j\) 的方案数。
\(dp_{i,j} = \left\{\begin{matrix} (\sum_{k = 1}^{a_{i - 1}} dp_{i - 1,k}) - dp_{i - 1,j},\ (1 \le j \le a_i)\\ 0,\ (j \ge a_i) \end{matrix}\right. \)
然后就会发现拿一个线段树记录 \(dp_i\) 这一维，每次的操作就相当于一个区间取相反数，区间加和区间赋值。
相当于拿一个维护区间乘合区间加的动态开点线段树，赋 \(0\) 就是乘 \(0\)，取相反数就是乘 \(-1\)。
\(\textup{Beautiful numbers}\)
每一位上的数字 \(0\) ~ \(9\)，\(\textup{lcm}\{1,2...9 \} = 2520\)。
考虑数位 dp。
设 \(dp_{i,j,k}\) 为当前是第 \(i\) 位，当前产生的数模 \(2520\) 为 \(j\)，当前应该整除的数为 \(k\)。
发现 \(2520\) 因数不多，所以第三维记离散化后的值。
int dfs(int pos, int lim, int sum, int mod) {
if (!pos)
return sum % mod == 0;
if (!lim && ~dp[pos][sum][lsh[mod]])
return dp[pos][sum][lsh[mod]];
int up = lim ? a[pos] : 9, res = 0;
for (int i = 0; i <= up; i ++)
res += dfs(pos - 1, lim && i == up, (sum * 10 + i) % 2520, i ? Lcm(i, mod) : mod);
if (!lim)
dp[pos][sum][mod] = res;
return res;
}