Home > OI > DP手记No.2

DP手记No.2


pku 1513
设F(i,j)表示前i堂课讲前j个主题的最小不满意度,则
F(i,j)=Min{F(i-1,k)+cost[k+1,j]}

pku 1579
大水题,用记忆化搜索即可

pku 1609
乍一看很容易设计出一个O(n^2)的DP,但是会超时,
注意到l和m的范围都很小,可以想像,
若以l为横轴,m为纵轴,所有点都在100*100的范围内。
想到了什么?数字三角形!
设F(i,j)表示走到点(i,j)时的最大值,则
F(i,j)=Max(F(i-1,j),F(i,j-1))+num[i,j]

pku 1631
最长不降子序列的O(nlogn)算法,略

pku 1633
设F(i,j,k)表示前i矮的障碍物,分成j组,难度值为k的方案数,则
F(i,j,k)=F(i-1,j,k)+(j-1)*F(i-1,j-1,k-1)+(i-1)*F(i-1,j,k-1)

pku 1636
依图中关系构图,形成多个连通分量,每个连通分量中的人必同时交换,
01染色并统计,再用背包算出答案即可。

pku 1644
递推题,题目叙述有点繁琐,按要求做就行了

pku 1649
范围太小了 直接枚举就行

pku 1651
将过程倒转,设F(i,j)为第i个数至第j个数操作后只剩第i个和第j个的最小分值,
枚举最后一次操作,则
F(i,j)=Min{F(i,k)+F(k,j)+a[i]*a[k]*a[j]}

pku 1655
任意指定根,首先用dfs统计每个结点的子树的结点个数,
这样删去该结点后,得到的若干森林,就是该结点的子树,
再加上包含该结点父结点的树,结点数为总结点数-1-子树结点数

pku 1661
预处理每个平台i从左边或右边跳下后落到的平台编号j1和j2,则
F(i)可以转移到F(j1)和F(j2),具体的方程略去

pku 1664
无序整数拆分问题
设F(i,j)表示将i分成j份的方法数,则
F(i,j)=
F(i-j,j) 每份都大于1
+F(i-1,j-1) 存在某份为1

pku 1671
可以根据不同的韵脚分类,设F(i,j)表示共有i行,韵脚有j种的不同的押韵方式,
则F(i,j)=F(i-1,j)*j+F(i-1,j-1)
这题比较“人性化”,省去了高精度计算

Categories: OI Tags: , , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: