[dp地狱训练]flag贴 - cool's Blog
[dp地狱训练]flag贴
cool
posted @ 2016年8月20日 19:30
in DP
, 632 阅读
作为大坡书院的一员，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）的
填坑中………………………………………………………………
2022年8月26日 12:49
Play Bartender Perfect Mix Game. We Unblocked it For You to Play at School. We at Unblocked Games 66 77 99 Unblocks All Games Like Bartender Perfect 2021. Unblocked Games GOGO is one of the game sites that are unblocked games at school that I secretly created. unblocked games for school, unblocked games 66 77 unblocked games 66,unblocked games happy wheels,unblocked games google sites,unblocked games 77,unblocked games 99.Play Bartender Perfect Mix Game. We Unblocked it For You to Play at School. We at Unblocked Games 66 77 99 Unblocks All Games Like Bartender Perfect 2021. Unblocked Games GOGO is one of the game sites that are unblocked games at school that I secretly created. unblocked games for school.
2022年12月23日 14:37
When we are travelling we need to find Restrooms, Bathrooms, or Public Toilets in the current location. Using Google Maps, Google Assistant, Alexa, iPhone Siri, and other location finder services helps you to get Nearest Public Toilets and Washrooms easily. restrooms near me Here we have discussed various location finder services that help you find the nearest public toilets near your current location where you are standing.