程设期末推荐练习

04:What a Ridiculous Election

注意搜的时候到同一个点有不同的状态,判断的时候不是判断是否vis,
而是要看当前的step和上一次的比较
dp[s][i][j]表示到达s状态用了i次操作一和j次操作二的结果
然后注意输出答案的时候要在终点枚举所有的ij

05:42点

写的时候想得复杂了,其实注意到可以交换顺序,所以这个东西其实只需要每次找两个数操作一下,然后放回去就好了。这样甚至考虑到了括号嵌套的问题

减法和除法是有顺序的,所以要两种都做一下

ref 这个题 这里面还要处理不能整除的情况,要用double = =

06:A Knight’s Journey

深搜注意回退删除标记 = =
用时间戳表示vis数组的时候,不是每个 case 开始的时候都清空,需要保证全局唯一

07:Sudoku

数独,多case要初始化,深搜回退要恢复状态= =

10:股票买卖

ll[i] 表示 i 左侧极差
rr[i] 表示 i 右侧极差
这样答案就是 $max{ll[i], rr[i + 1]}$

先用 ll[i] 得到 i 左侧最小的数和a[i]的差,然后对ll[i]求个前缀 max 就好了

12:开餐馆

dp[i] 最后一个在 i 开,最大的价值
答案是数组的最大值

11:Tour POJ 2677

想了好几天,把一来一回的路径拆开,考虑$dp[i][j] 表示 1..i 和 1..j 两条路径$,
然后考虑下一个点(i)是从谁接过来的

https://blog.csdn.net/xiaoxiaoluo/article/details/7636592 这里人为要求 $i \geq j$

https://blog.csdn.net/ECNU_LZJ/article/details/71211855 这个更直观,把路径反向,
方便转移

14:DNA

调了半天,甚至还换了种思路写,最后发现问题是在于求重叠部分的长度又写错了

首先没想到的是,如果一个串被另一个包含了,那么短的直接删掉就好了

思路一:长度很少,枚举全排列,拼起来

思路二:状压dp,$dp[st][i]$表示已经拼了st里面这些字符串i是最后一个的答案,记忆化搜之

求重叠部分的写法:

1
2
3
4
5
6
int res = std::min(len[a], len[b]);
while (res) {
if (strstr(s[b], s[a] + len[a] - res) == s[b]) break;
--res;
}
return res;

论善用strstr的重要性

13:上机

按顺序考虑,前i个人的结果受前i-1个人的结果和第i与第i-1的顺序的影响

设计:$dp[i][l][r]$表示处理到第i个人,左侧 / 右侧有没有人

转移:dp[i][k][t] = std::max(dp[i][k][t], dp[i - 1][j][k ^ 1] + a[i][k + t]);

注意带如果第i个人左侧的状态是k,那么对于第i-1个人而言,他右侧的状态就是k ^ 1

注:用k + t简化,a[i][0]就是都没人,a[i][1]就是有一个,a[i][2]就是两侧都有人

这里的j是不造成影响的,转移的过程中要考虑每一个j0 / 1