[dp地狱训练]flag贴 - cool's Blog

[dp地狱训练]flag贴

cool posted @ 2016年8月20日 19:30 in DP , 281 阅读

作为大坡书院的一员,dp能力一直处于垫底,被强行拉来艹dp题。

 

现在

[51nod1468]

一个h*w的矩阵有n个点不能走,求路径个数。

状态f[i]表示第i个点走到右下角,不经过障碍的路径条数。

[51nod1202]

求序列的所有不同子序列。

f[i]表示以i为结尾的不同子序列个数。

f[i]应该由不同的a[j]转移,这样是n^2的,直接记sum,就O(n)了

[51nod1201]

将N划分成若干不同整数和的方案。

f[i][j]表示从选i个数和为j的方案

f[i][j] = f[i-1][j-i]+f[i][j-i] O(n^1.5)

这道题没想出来,最后问的黈力。主要对于50000不够敏感,没有想到二维的状态。

[51nod1055]

将数从小到大排序后,求等差子序列个数。

枚举每个数,然后向两边扫转移即可。O(n^2)

黈力说不从小到大排序也可以做,感觉很厉害。

[51nod1354]

求多少个子序列的积为K(K<=1e8)

f[i][j]表示前i个数乘积为j的子序列个数,复杂度O(n^1.5)

[51nod1376]

求LIS个数。

p[i]+=p[j](j<i,a[j]<a[i],f[j]=f[i]-1)

然后按f排序后,里面按i排序,然后用树状数组就可以了。O(nlogn)

[51nod1259]

将N分成若个数的和的方案。

考虑和1201的关系。我们可以这样考虑,计算f[j]表示用1-n^0.5的数的和表示j的方案

g[j]表示用n^0.5-n表示和为j的方案。

f可以用完全背包算。g用1201算。都是O(n^1.5)的

填坑中………………………………………………………………


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee