离散化写挫了就wa了n发。。
先按照右端点排序，设dp[i]为铺满1到i的最小价值，注意是铺满，那么就可以在这里更新dp[r[i]]=min(dp[j])+v[i] l[i]<=j<=r[i]，注意这里有一个-1，对于左端点来说，因为如果两个线段相邻二不相交，比如(1,2)(3,4)，这样其实也是可以的。这里的话，如果直接把端点离散化，就会导致后面的操作很复杂，因为要考虑相邻中间有没有空（我也是这么错的），所以不如直接在一开始读入左端点的时候就给他-1，这样之后就不用什么多余的操作了，直接每次线段树查询最小值即可。 继续阅读“[DP][线段树][离散化][细节][坑] XDOJ 1324”
数位DP入门题，其实只要搞懂dp[i][j]存的是什么就行了。
用搜索解法的话，每次相当于枚举了比当前位小的所有数字，然后需要记录下是不是上界（第一位）。就题目而言的话还需要记录前面一位是不是6（这决定了当前位可不可以是2）,记忆化的话有一点是当如果是上界（第一位）的时候是不能记忆的，因为记忆话那个其实是存了第len位长的前缀为/不为6的当前位可以从0到9的所有数中的答案，注意这里这个东西是和给定的什么串无关的，同时他也不能有关，因为这个不能把信息完全表示出来。所以只有在不是上届的时候才保存记忆化结果。 继续阅读“[DP][数位DP] HDU 2089 不要62”
https://cn.vjudge.net/problem/HDU-6377
不懂dp的我根本想不到是用dp来做。。。emm
如果把每一对情侣两个人看成等价的，那么可以构造出来，状态只与两个因素有关：一共有多少对情侣；有多少对情侣是坐在一起的，用dp[i][j]来表示有i对情侣，其中j对坐在一起的方案数，在这个的基础上可以往里面继续插入一对新的情侣，而插入的方式和结果总共会导致五种变化，每次都考虑一下，刷表即可。预处理出所有的可能情况，接下来每次输入的时候过一遍dp[n][i]就行了。由于把两个人看成了一样的，所以最后还要乘上2^n，用快速幂即可。 继续阅读“[DP][计数DP][组合数学] HDU 6377 度度熊看球赛”
算是学到了缩点构造新图的方法吧emm有点笨
有环的图一般都有点难倒腾，所以这种都是遇见了先求scc，变成DAG以后再想办法求解。
分析题意后可以发现，对于DAG，求出来的其实是一条路径，因为如果有分叉的话分叉的不同子树之间就没有办法互通了。令每个缩点的权值为含点的个数，这样就转化成了DAG上的最长路问题了。
错误：scc每次都会出现漏初始化错误。。。还有就是缩点之后的节点标记与原来的节点意义不同，要注意。
我上次wa两个小时是什么时候？？？妈的这个题格式。。。提示一个PE能死啊我去
直接暴力dp很好想但是复杂度爆炸，经过转换后可以把i和j分离开，然后j的那一部分就成了独立的只跟j有关的，这时候就可以把他当成一个新的量，然后求的时候就是在weight(j+1,i)<c的条件下（可以发现这其实是一个滑动的窗口）求出使得wav最小的j，就很像基本的dp了，只不过求最小j的时候用单调队列优化了。 继续阅读“[训练指南][单调队列][DP] 滑动窗口单调队列优化线性dp 输出格式坑 LA3983”
题意给出森林，让在放置的点数尽量少的情况下保证每条边都被点覆盖到（乍一看二分图匹配？），然后在此前提下再要求被两个点同时覆盖到的边最多。两个需要解决的的：1 怎么把这个多目标最优化解决了 2 怎么处理不同节点之间的影响
