最近做的无聊事-FrozenTurtle篇
十一月 10th, 2009大多数是水.....部分感觉比较有特点的加*..不定期更新
线性动态规划
VOJ1355 车队过桥问题 f[i]表示前i部通过最短时间,预处理t[i,j]表示i到j的最慢速度,w[i]表示前i部车的重量和,f[i]:=min(f[k]+l/t[k+1,i])
VOJ1292 火车票 f[i]:=min(f[k]+cost(k,i))
*VOJ1474 雷曼兔(csapc) 排序后类似Lis
VOJ1571 笨笨的导弹攻击 最长上升下降混合子序列...orz
*VOJ1696 爱国者的周期 同上 判断周期用 (f[j]-1)mod(t*2)<t
VOJ1421 更换轮胎 f[i,j]表示第i圈用j种车胎所需最短时间,另开l[i]表示第i圈的最短时间用的车胎号码
*Open09ski 滑雪 f[i,j] 表示于i时间j能力所能得到最多滑雪数 f[i,j]:=max(f[i-1,j],f[i-d[g[i]],j]+1(j>=c[k]),f[i-l[k],0](0为i-l[k]时最大达到))g[i] 表示能力为i时 所能滑的最优轨道号码
VOJ1331 看球的巴士 f[i]:=min(f[j]+1)(abs(s[i]-s[j])<=d)or(abs(s[i]-s[j])=i-j) f[0]=0 f[1]=1
Cai0715-1 一起去打cs f[i,j]:=min(f[i-1,j]+b[i],f[i-1,j-a[i]]) 状态 完成i-1件作业耗甲j时间时,所需乙最短时间 决策 第i件交给谁做
VOJ1118 统计字符串 预处理g[i,j] i-j间字符串个数
*VOJ1037 搭建双塔 f[i-1,j] 不放 f[i-1,j+h[i]] 放到矮塔仍为矮塔 f[i-1,h[i]-j]+j 放到矮塔变成高塔 f[i-1,j-h[i]]+h[i] 放到高塔
背包问题
VOJ1625 精卫填海(HOI) 01背包
VOJ1418 公司聚会 倒推01背包 f[p[i],j]:=max(f[p[i],j],f[p[i],j-k]+f[i,k]),最后判断职人1号是否更优.
VOJ1544 GF 裸两维背包
VOJ1392 拼拼图的小杉 伪01背包 f[i,j]表示前i件物品选j件,所需最小集合数,g[i,j]表示最后一个集合已填充容量
VOJ1198 最佳课题选择 f[i,j] 前i种论文完成j件所需最短时间 f[i,j]:=min(f[i-1,k]+a[i]*(j-k)^b[i]) 0<=k<=j (分组背包也可做)
*VOJ1313 金明的预算方案 有依赖背包->分组背包
树形动态规划
*VOJ1180 选课 基础树形.f[k,t]:=max(f[r[k],t],max(f[l[k],t-1-i]+f[r[k],i]+s[k])) (i=1..t-1)
区间动态规划
*VOJ1242 邮局问题 f[i,j] 1到i的村庄,修j个邮局的最小距离,预处理d[i,j],表示于i,j中点修建的距离和,f[i,j]:=min(f[k,j-1]+d[k+1,i])
*VOJ1347 乘积最大 f[i,j]:=max(f[k,j-1]*s[k+1,i])
VOJ1218 数字游戏 预处理s数组后同乘积最大 f[i,j]:=max(f[k,j-1]*s[k+1,i])
多进程动态规划
VOJ1493 传纸条 f[i,j,k]第i步,A的x位置于j,B的x位置为k的最大值
*VOJ1143 三取方格数 同上,四维,第一维可用循环数组消去.
*VOJ1014 旅行商简化 f[i,j]:=min(f[j,j-1]+s[j-1,i],f[i,j-1]+s[j-1,j]) (i>=j) f[i,j]=f[j,i] 避免跳过路程,必须从近的一点j进行扩展
VOJ1680 距离 字符串距离 f[i,j]:=min(f[i-1,j-1]+d[i,j],f[i-1,j]+k,f[i,j-1]+k)
VOJ1111 水果店 总长度-最长公共子序列
状态压缩
*VOJ1424 炮兵阵地 把每一行状态用二进制存储于一个longint中,预处理每一行可能摆放,存于p[i,j],由于一行只与前两行有关,
f[i,j,k]:=max(f[i-1,k,t]+addnum(p[i,j])) f[i,j,k] 表示到第i行,第i行摆放为p[i,j],第i-1行为p[i-1,k] 时的最多炮兵数
Matrix67-0817 多米诺 类似上一题,状态压缩每一行状态,70分
递推
VOJ1232 核电站问题 连续N个东西,不能选连续m个的选法总数
VOJ1408 古韵之乞巧 f[i,k+1]:=f[i,k+1]+f[j,k] 以s[i]结尾的长为k+1的方案数
记忆化搜索
VOJ1547 逆转，然后再见 诡异的记忆化搜索..
VOJ1011 滑雪 同上
