题意给一个字符串和单词字典，问把字符串分割成词典中存在的单词可以有多少种方法（单词可以重复使用）首先是像dp那样考虑，令d(i)为从第i个字符开始到结束的字符串的方案数，然后可以得出d(i)=sum{d(i+len(x))|单词x是S[i,l]的前缀}。然后就是找一个串有多少个单词前缀了。。。字典树搜索即可搞定，就是在Trie中查找S[i,l]，一路查过去把遇到的是单词节点的地方加上那里的d就可以了。
继续阅读“[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942”
[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983
我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去
直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”
[训练指南] 树形DP 多目标最优化 有优先级的优化量 UVa10859
题意给出森林，让在放置的点数尽量少的情况下保证每条边都被点覆盖到（乍一看二分图匹配？），然后在此前提下再要求被两个点同时覆盖到的边最多。两个需要解决的的：1 怎么把这个多目标最优化解决了 2 怎么处理不同节点之间的影响