1 Power收集

设dp[i][j]为走到第i,j个位置的最多能量,考虑每一个状态都从上一层dp[i-1][j-t ~ j+t]转移而且取max,于是简化状态每一次用堆维护上一层的最大数(std应该是单调队列然而时限比较善良于是堆也能水过)然后检查当前位置和堆顶元素位置,不满足就pop。然后取堆顶转移

关路灯

区间……没做出来看题解了……

设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]转移来

小a和uim之大逃离

脑残没想到看题解系列

知道状态一定有第四维,也知道一定有前两维……然而就是脑残想不到可以化成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)统计答案。

 矩阵取数游戏

本质上就是关路灯

套一个高精度就行了

我设的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转移

注意最外面一层是从大到小枚举长度

最长公共子序列(LCS问题)

傻比题既视感

大概是这样:因为是一个排列,考虑把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就可以过

有线电视网

关键词:树上背包,傻比题。

设状态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 );

加分二叉树

破区间dp,什么玩意

对于每个子树,枚举它的根节点(>=L <=R)然后暴力dp更新

1.设计状态dp[i][j]表示在中序遍历中i~j这段区间代表的子树的最大加分

2.注意空树的处理 if (i>j) return 1;

[HAOI2012]音量调节

傻比题,纯粹是为了有时间tuifei

然而交了三遍才过,变量重名竟然都检查不到。

就是些**样例 -Yansir

[HAOI2009]逆序对数列

看题解才过去……

真是道好题

设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 

分类: DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.