tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

USACO DP动规 完整版


Wizard 1.单调队列优化
①土地并购 (Land Acquisition, 2008 Mar) ②干草塔 (Tower of Hay, 2009 Open) ③又买饲料 (Buying Feed, 2010 Nov) ④玉米实验 (Cornfields, 2003 Mar) ⑤修剪草坪 (Mowing the Lawn, 2011 Open)

>2. 树型
①焊接 (Soldering, 2011 Open) ②产奶比赛 (Milk Team Select, 2006 Mar) ③道路重建 (Rebuilding Roads, Feb 2002) ④手机网络 (Cell Phone Network,2008 Jan)

3. 背包问题续
①电子游戏 (Video Game Troubles,2009 Dec) ②最少找零 (The Fewest Coins, 2006 Dec) ③三个代表 (Jersey Politics, 2005 Feb) ④录制唱片 (Raucous Rockers, 1996 Qualifying Round)

4. 背包问题
①股票市场 (Stock Market, 2009 Feb) ②奶牛会展 (Cow Exhibition, 2003 Fall) ③太空电梯 (Space Elevator, 2005 Mar)
I

④平分子集 (Subset Sums, 1998 Spring)

5. 区间型
①提交作业 (Turning in Homework, 2004 Open) ②抢鲜草 (Grazing on the Run, 2005 Nov) ③最优回文 (Cheapest Palindrome, 2007 Open) ④智取金币 (Treasure Chest, 2010 Dec)

6. 其他一
①打扫食槽 (Cleaning Up, 2009 Mar) ②奶牛自行车队 (Cow Cycling, Feb 2002) ③滑雪缆车 (Ski Lift, 2006 Mar) ④奶牛飞盘队 (Cow Frisbee Team, 2009 Mar)

7. 其他二
①滑雪比赛 (Bobsledding, 2009 Dec) ②滑雪课程 (Ski Lessons, 2009 Open) ③方形牛棚 (Big Barn, 1997 Fall) ④接住苹果 (Apple Catching, 2004 Nov) ⑤公司利润 (Profits, 2011 Jan)

II

土地并购
(Land Acquisition,2008 Mar)

首先我们按长与宽都递减の排序,如果有一个矩形长宽 都不如另一个矩形,那么可以忽略它。 剩下的矩形可以看做,长度递增而宽度递减。 F[i]表示前 i 个矩形的最小花费。 那么有 f[i]=min(f[j]+x[j+1]*y[i])(j<i) 当然 O(N^2)的算法是对不完的。 斜率优化不再赘述。

III

干草塔
(Tower of Hay, 2009 Open)
显然,将塔看作一个面积一定图形,要使其最高,必须 最瘦。 F[i]表示从 n->i 层的最底层的宽度。 F[i]=min(sum[j-1])-sum[i-1];(N>j>i) 显然,j 越小 F[i]越优。 G[i]自然用来记 n->i 最多的层数。 当然 F[i]>=F[j], 即: F[j]<=min(sum[j-1])-sum[i-1]。 Sum[i-1]<= sum[j-1] -f[j],sum[i-1]是递减的,所以 当第一个 i 满足条件后,之后的 i-1~1 都是满足的。
for (int i=n;i;--i) { while (h<t && f[q[h+1]]<=sum[q[h+1]-1]-sum[i-1]) h++; //找出最后一个满足的 f[i]=sum[q[h]-1]-sum[i-1];g[i]=g[q[h]]+1;q[++t]=i;//入队 while((t>h)&&(f[q[t-1]]-sum[q[t-1]-1]+sum[q[t]-1]>f[q[t]])) --t,q[t]=q[t+1]; }

IV

又买饲料
(Buying Feed, 2010 Nov)

F[i][j]表示到第 i 个商店时,一共买了 j 那么多饲料 的最小花费。 F[i][j]=min{f[i-1][k]+(j-k)*v[i-1]}+j*j; (k<j&&(j-k<=c[i-1])) 用单调队列优化: F[i][j]=min{f[i-1][k]-k*v[i-1]}+j*v[i-1]+j*j 这 样取最小值的循环里就只与 k 有关,此时维持一个 f[i-1][k]-k*v[i-1]的递减单调序列,每次选择将为 O(1)。

V

玉米实验
(Cornfields, 2003 Mar)

首先, 我们可以使用 RMQ 来查询每排的最小值最大值, 即初始化需要 N 个 RMQ,O(N^2*log(N))是可以接受的。 之后的 K 次询问,每次询问 B 排的最值,O(N*K)可以 AC。

VI

修剪草坪
(Mowing the Lawn, 2011Open)

f[i]表示 i 不要的最小舍弃值。 for(int i=0;i<=n+1;i++) { if(q[s].n<i-k-1&&s<t)s++;//队列长超过 k 头指针+ f[i]=q[s].v+a[i];//队列开头的是最小的,因此舍弃它 while(q[t].v>f[i]&&t>=s)t--;//维持一个递增序列 q[++t]=Cut{f[i],i}; //入队 } Cout<<sum-f[n+1];

VII

焊接
(Soldering, 2011 Open)

VIII

产奶比赛
(Milk Team Select, 2006 Mar)

类似于道路重建,即 f[x][i]表示节点 x 分配 i 个关系 能够取得的最大奶量,由于可以是散点,所以可以将这 i 个 关系随意分配给儿子们,最后取最好的方案。 关于如何去最佳方案,我们可以用背包分配。

IX

道路重建
(Rebuilding Roads, Feb 2002)

F[i][j]表示以第 i 个节点的子树要变为只有 j 个儿孙 (自己也算)的树所需要剪得最少的边。 然后对儿子们进行背包分配,得出他们各留多少子孙, 使花费最小。

X

手机网络
(Cell Phone Network, 2008 Jan)
相当于皇宫看守。 F[x][0] 表示不在 x 上放但监控 x 的节点们(包括 x 自 己)的最小费用; F[x][1] 表示不在 x 上放但监控 x 的节点们(不一定包 括 x 自己)的最小费用; F[x][2] 表示在 x 上放且监控 x 的节点们的最小费用; 则有:

~~~~~~T 必须由他的儿子监控

~~~~~~T 不一定由他的儿子监控

~~~~~~T 自己监控

XI

电子游戏
(Video Game Troubles,2009 Dec)

即 “金明的预算方案”加强版,每个游戏平台可带 10 个游戏,所以他们可以处理为 2^10 个不同的商品且分为一 组。那么可以分为 k 组,每组有 1024 个游戏,每组选 1 个 或 0 个。 之后即为分组背包。

XII

最少找零
(The Fewest Coins, 2006 Dec)

直接将土豪的补钱视作面值为 ’-’ 的纸币,并且有无限 张。那么可以当做“有限硬币问题”解决,即取得面值 x 所 需要的最少硬币数。

XIII

三个代表
(Jersey Politics, 2005 Feb)

类似于三角形牧场,我们只关心两个选区的 Jersey 牛 是否能够超过半数。使用 01 背包拓展 f[i][j]成立的情况, 最后检查是否有 i,j 都超过 500 的成立。不过貌似方案要另 找,且数据大了要爆。

XIV

录制唱片
(RaucousRockers,1996QualifyingRound)

f[i][j][k] 表示在前 i 张唱片、录到第 j 分钟、录到第 k 首歌所录得最多歌曲数。 f[i][j][k]=max{前一分钟的歌曲数, 前一首歌的歌曲数, 把第 k 首歌在当前位置放进去的歌曲数(如果可以)} 。
for(i=1;i<=m;i++) for(j=1;j<=t;j++) for(k=1;k<=n;k++){ if(j==1) f[i][j][k]=max(f[i-1][t][k], //第 i 张唱片 //第 j 分钟 //第 k 首歌 //换唱片 f[i][j][k-1]);

//前一首歌的歌曲数 //前一分钟的歌曲数(下同) else //没有换唱片 f[i][j][k]=max(f[i][j][k-1], f[i][j-1][k]); if(len[k]<j) //没有换唱片 f[i][j][k]=max(f[i][j][k],f[i][j-len[k]][k-1]+1); //把第 k 首歌在当前位置放进去的歌曲数 (下同) if(len[k]==j) //换唱片 f[i][j][k]=max(f[i][j][k], f[i-1][t][k-1]+1); }
XV

股票市场
(Stock Market, 2009 Feb)

显然 f[i]表示第 i 天所能拥有的最大钱数。 我们第 i 天赚得越多,f[i+1]就会越大。但是我们不能 用所有钱去买某只赚得最多的股票,因为那样可能剩下一些 零钱,或是直接买次一等的但更多的反而更好。 那怎么分配呢? 将 v[i+1]-v[i]视做价值,我们发现每天做一次 01 背包 即可。
XVI

奶牛会展
(Cow Exhibition, 2003 Fall)

二维 01 背包,因为背包只能解决正数的问题,所以我 们整体偏移 1000, 那么以 1000 为 0 点, 在 f[1000][1000] 之后寻找答案,使 i+j 最大即可。

XVII

太空电梯
(Space Elevator, 2005 Mar)

首先按安全高度排序,因为安全高度小的要想被利用, 只能呆在最下面。 之后依次添加,只要在安全高度以内,有多少价多少。

XVIII

平分子集
(Subset Sums, 1998 Spring)

for(int i=1;i<=N;i++) for(int j=N*(N+1)/4;j>=i;j--)//01 背包 dp[j]+=dp[j-i]; cout<<dp[N*(N+1)/4]/2; //二分之总数的情况除以 2 是因为两部分对称

XIX

提交作业
(Turning in Homework, 2004 Open)

由大区间推出小区间。 F[i][j][0] 表示在整个 i~j 区间里只有 i 这个作业交了; F[i][j][1]表示在整个 i~j 区间里只有 j 这个作业交了; 初始化:
dp[1][n][0]=max(a[1].x,a[1].t)在 1-n 区间内只交了 1 作业 dp[1][n][1]=max(a[n].x,a[n].t)在 1-n 区间内只交了 n 作业

状态转移方程: dp[i][j][0]=min(max(dp[i-1][j][0]+x[i]-x[i-1],t[i], max(dp[i][j+1][1]+x[j+1]-x[i],t[i])) dp[i][j][1]=min(max(dp[i][j+1][1]+x[j+1]-x[j],t[j]) ,max(dp[i-1][j][0]+x[j]-x[i-1],t[j]))

XX

抢鲜草
(Turning in Homework, 2004 Open)

奶牛逃跑型 dp. f[i][j][1]表示吃完 i~j 后停在 i 的最小损失,f[i][j][0] 表示吃完 i~j 后停在 j 的最小损失。 状态转移方程:
f[i][j][1]=min(f[i-1][j][1]+(N-i-j+1)*(a[i]-a[i-1]), f[i-1][j][0]+(N-i-j+1)*(a[i]+b[j])); f[i][j][0]=min(f[i][j-1][0]+(N-i-j+1)*(b[j]-b[j-1]), f[i][j-1][1]+(N-i-j+1)*(a[i]+b[j]));

XXI

最优回文
(Cheapest Palindrome, 2007 Open)

F[i][j] 表 示 将 i~j 变 为 回 文 串 的 最 小 代 价 , 显 然 f[i][i]=0。 状态转移方程: if(a[i-1]==a[j+1])f[i-1][j+1]=f[i][j] f[i][j]=min(f[i-1][j]+v[a[i]],f[i][j-1]+v[a[m-j+1]])

XXII

智取金币
(Treasure Chest, 2010 Dec)

F[i][j] 表示先手在区间 i~j 的最大值。 G[i][j] 表示后手 在区间 i~j 的最大值。 f[i][j]=max(a[i]+g[i+1][j],a[j]+g[i][j-1]) g[i][j]=sum[j]-sum[i-1]-f[i][j] 所以 F[i][j]=sum[j]-sum[i-1]-min(f[i+1][j],f[i][j-1])

XXIII

打扫食槽
(Cleaning Up, 2009 Mar)

显然,f[i]定义为前 i 头牛所使用的食槽最少时间。 F[i]=min{f[j]+calc(j+1,i)}(j<i) Calc 表示计算区间 j+1~i 的不同总类数。 要在最开始计 算前一次性统计出来(Hash)。 当然,O(N^2)是对不完的。

XXIV

奶牛自行车
(Cow Cycling, Feb 2002)

显然,每只奶牛只会担任一次领队,卸任后可以舍弃, 毕竟只要有一头奶牛到达就行。 F[i][j][k] 表示现在由第 i 只奶牛领跑,共跑了 j 圈, i 已消耗 k 体力。 状态转移方程: F[i][j+p][k+p^2]=min(F[i][j+p][k+p^2],f[i][j][k]+1) F[i+1][j][j]=min(F[i+1][j][j],f[i][j][k])

XXV

滑雪缆车
(Ski Lift, 2006 Mar)

显然,f[i]表示前 i 座山修的最少支柱。 F[i]=f[j]+1(j 合法) PS:j 合法即:1.i-j<=k 2.i~j 的斜率不能小于 i, j 之中的最大斜 率,即不能穿越山峰

XXVI

奶牛飞盘队
(Cow Frisbee Team, 2009 Mar)

F[i][j]表示前 i 个数的组合 mod F==j 的方案数。 状态转移方程: F[i][j]+=f[i-1][j]; F[i][(j+a[i])%F]+=f[i-1][j];

请脑补答案(及过程)mod 10^8 部分

XXVII

滑雪比赛
(Bobsledding, 2009 Dec)

F[i]表示在 i 点前能达到的最大速度。 for(int i=1;i<=n+1;i++){ int start_speed=min(f[i-1],s[i-1]);//t0 int delta_speed=start_speed-s[i];//△t int distance=t[i]-t[i-1];//s int tmp=distance-abs(delta_speed); //是否可以加速到最大 if(tmp<0) f[i]=start_speed+distance; else f[i]=tmp/2+max(s[i],start_speed); }
XXVIII

滑雪课程
(Ski Lessons, 2009 Open)

for(int i=1;i<=t;i++){ for(int j=1;j<=100;j++){ f[i][j]=f[i-1][j]; if(ke[i-1][j])f[i][j]=max(f[i][j],g[ke[i-1][j]]); if(i-po[j]>=0)f[i][j]=max(f[i][j],f[i-po[j]][j]+1); g[i]=max(g[i],f[i][j]); } }

XXIX

方形牛棚
(Big Barn, 1997 Fall)

F[i][j]是以 i,j 为右上角的最大正方形。 if(a[i][j]==’#’)f[i][j]=0; else F[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1

XXX

接住苹果
(Apple Catching, 2004 Nov)

F[i][j]表示第 i 时间,已经移动了 j 次所取得的最大值。 状态转移方程: F[i][j]=f[i-1][j]+a[(i-1)%2][i-1] +f[i-1][j-1]+a[i%2][i-1]

XXXI

公司利润
(Profits, 2011 Jan)

最大连续子段和。 F[i]=max(f[i-1],0)+a[i]

XXXII


推荐相关:

1D1D动态规划优化初步

例题 2:土地购买题目来源:USACO Monthly, March, ...第一种可能可以通过树形 DP 解决,问题就在于第二种...你可以 选择原地不动,也可以选择按照一个特定的方向...


动态规划47题

dp动态规划练习 动态规划练习【题目一览】第一题 ...总分【问题描述】 学生在我们 USACO 的竞赛中的得分...迷宫中的某些区域是障碍物,机器人不能移 动到那里...


USACOchapter6

(具体处理时,我们可以不用减法,只要注意加的顺序就可以了) 对于特殊的 dp[2],我们只要特殊处理即可。 这样时间复杂度降为 O(n)。 USACO 6.1.3 A ...


环形DP学案

的能量项链,p1218 的数字 游戏,usaco 第一章中破碎的项链,rqnoj 上 p490 的石子合并等问题.环形 DP 相对线性 DP 来说, 难度增加了, 对于环形 DP 这一类...


USACO 2.2 Subset Sums集合 解题报告

USACO 2.2 Subset Sums集合 解题报告_IT/计算机_专业资料。USACO 2.2 Subset...然后 DP 方程就是: f[i][j] = f[i - 1][j] + f[i - 1][j -...


bzoj刷题总结列表

1230: [Usaco2008 Nov]lites 开关灯线段树。 区间...Bool 型动规。 1026: [SCOI2009]windy 数令 f[...ans=拓展次数 1047: [HAOI2007]理想的正方形 dp,...


动规

动规.txt 恨一个人和爱一个人的区别是:一个放在...引言:本人在做过一些题目后对 DP 有些感想,就写 ...(buylow.pas/c/cpp) 来源: USACO 4-3-1 【...


动态规划教程——pascal语言描述

本人在做过一些题目后对 DP 有些感想,就写了这个...其实按照我的理解(动规涉及最优决策,递推是 单纯...(money.pas/c/cpp) 来源:USACO 2.3 【问题描述...


usaco数据

USACO 1.1.4 Broken Necklace 枚举+搜索或 DP 1 次 ac USACO 1.2.1 Milking Cows Milking Cows Three farmers rise at 5 am each morning and head for ...


USACO Tips 分析

USACO 提示题号 1.1.1-1 1.1.1-2 1.1.2-...1.3.2-4 A Game 55% 博弈 (DP) 9. 1.3....(恶心) 备忘录式动态规 图论 穷举 解方程(搜索) ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com