1 Power收集
设dp[i][j]为走到第i,j个位置的最多能量，考虑每一个状态都从上一层dp[i-1][j-t ~ j+t]转移而且取max，于是简化状态每一次用堆维护上一层的最大数（std应该是单调队列然而时限比较善良于是堆也能水过）然后检查当前位置和堆顶元素位置，不满足就pop。然后取堆顶转移
2 关路灯
区间……没做出来看题解了……
设dp[i][j][0/1]表示把区间[i,j]内的所有灯全部关闭并停在i（第三维是0）或j（第三维是1）处，已经消耗的电能
枚举区间大小转移。注意dp[i][j][0]可从dp[i+1][j][1]转移来，dp[i][j][1]能从dp[i][j-1][0]转移来
脑残没想到看题解系列
知道状态一定有第四维，也知道一定有前两维……然而就是脑残想不到可以化成O(nmk)，还傻傻的以为是O(n2m2)……
只允许这一次脑残了……
我们设dp[i][j][p][0/1]表示从1,1用随便什么路径走到i,j点，并且disA-disB=p（%k意义下，所有没有负数，尽管应该有）时的合法方案数
那就是dp[i-1][j][ ( (p-mapx[i][j])%k +k)%k ][1]+dp[i][j-1][ ( (p-mapx[i][j])%k +k)%k ][1]
（逆序还原上一个状态的p，因为现在是A走达到了p，那么没经过i,j之前一定是p-mapx[i][j]）
另一个状态同理。
注意随时%1000000007
最后O(NM)统计答案。
4 矩阵取数游戏
本质上就是关路灯
套一个高精度就行了
我设的dp[i][j]表示这一行余下区间[i,j]的时候的最大得分（好像是得分？还是什么……？）
每一次从dp[i-1][j]+pow(2,m-(j-i)-1)*mapx[i-1][j]和dp[i][j+1]+pow(2,m-(j-i)-1)*mapx[i][j+1]取max转移
注意最外面一层是从大到小枚举长度
傻比题既视感
大概是这样：因为是一个排列，考虑把B串做一个映射，标记下每一个元素（1~n）在B串中的下标
然后让A串通过映射构造一个新的串，因为是公共序列问题，所以只要在新串中按照顺序出现的就是A与B重合的。
比如说，6在B中是[19]，那就把6映射到19（codex[6]=19） 3在B中是[22] 也映射过去
那么假设6在A中是[2]那么新串C[2]=codex[A[2]] 所以C[2]=19
3在A中是[5]，那么C[5]=codex[A[5]] C[5]=22
那么显然在A串中，3在6后面，而且B串中3也在6后面，这样如果把A中3 6替换为3 6在B中的下标，那一定是递增的。
最后nlogn做法的LIS就可以过
6 有线电视网
关键词：树上背包，傻比题。
设状态f[i][j]表示结点i连接j个用户的最大赚取（支付的钱-花费）然后枚举子树暴力转移一波就行
注意计数，枚举到一颗新的子树，现在结点的[最大连接用户(叶子)数目+=子树的最大连接数目]
然后j从0循环到最大连接数目取max
dp[nownode][i] = max ( dp[nownode][i] , dp[nownode][i-j] + dp[v][j] – edge[prex].w );
7 加分二叉树
破区间dp，什么玩意
对于每个子树，枚举它的根节点(>=L <=R)然后暴力dp更新
1.设计状态dp[i][j]表示在中序遍历中i~j这段区间代表的子树的最大加分
2.注意空树的处理 if (i>j) return 1;
看题解才过去……
真是道好题
设dp[i][j] 表示前i个数（1-i）出现j个逆序对有多少方案，可知dp[1][0]=1；
考虑把第二个数分别放在第0个位置（第一个数之前），第1个位置，第2个位置……假设现在的i=2则有dp[2][2]=dp[1][2]+dp[1][1]d+dp[1][0]
也就是分别放在哪个位置上（0,1,2 ps注意前后括号里的对应），还欠缺的逆序对需要用之前的i-1个数补。(dp[1][0] dp[1][1],dp[1][2])
归纳总结一下：
1.dp[i][j]=∑dp[i][k] ( max(j-i+1,0) ≤ k ≤ j )
2.用前缀和优化转移，O(n2)
直接令dp[i][j]代表之前的∑dp[i][k] (0 ≤ k ≤ j )
然后转移可以O(n2) : dp[i][j]=dp[i-1][j]-dp[i-1][j-i] +dp[i][j-1]
10 跳舞
（背景）很像紫书上的那个Tango
设计状态dp[i][j]表示踩到了第i个箭头的时候踩了j次，此时的最大得分
可以发现决策就两个：踩，得分；或者不踩，扣分。
所以从dp[i-1][j-1]+socre[i] , dp[i][j]-score[i]转移
特判j%t=0的情况，此时踩多加分，不踩不多扣分
11