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