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

usaco bookshelf


1.

书架{bookshelf.pas/c/cpp}

usaco2012 OpenGold usaco2012 Open Gold 【问题描述】 有 N(1 <= N <= 100000)本书,每本书有一个宽度 W(i),高度 H(i),(1 <= H(i) <= 1,000,000; 1 <= W(i)

<= L)。 现在有足够多的书架,书架宽度最多是 L (1 <= L <= 1,000,000,000),把书按 顺序(先放 1,再放 2.....)放入书架。某个书架的高度是该书架中所放的最高 的书的高度。 将所有书放入书架后,求所有书架的高度和的最小值? 【文件输入】 第一行: 两个整数 N 和 L。 接下来 N 行,每行包含两个整数 H(i) 和 W(i)。(1 <= H(i) <= 1,000,000; 1<= W(i) <= L)。 【文件输出】 一行: 所有书架高度之和的最小值。 【输入样例】 5 10 5 7 9 2 8 5 13 2 3 8 【输出样例】 21

【样例说明】 分三个书架, 第一个一本书[1] (高度 5, 宽度 7), 每二个书架三本书[2\3\4] (高度 13, 宽度 9), 第三个书架一本书[5] (高度 3, 宽度 8)。 这道题的原型是 POJ 的 3017,只是 W[I]换成数列中的权值而已; 对题目进行分析,不难得到动规方程 f[i]=min(f[j]+max(h[j+1],h[j+2],h[j+3]....h[i]))其中 w[j+1]+w[j+2]+...w[j]<=l; 但是这只是 O(n^2)的做法,必须想出优化办法; 首先我们会发现一个 i 状态会与许多 j 的子状态相关, 这种情况大多都是与单调 队列的优化相关;但是这道题并不这么明显; 首先,我们向求 max 的 h[j]值方向思考,不难维护出一个单调递减,队头到 i 的 w[i]之和小于 l 的最大值单调队列;但是这样就将 f 的值给忽略掉了; 所以我们需要想出 f 数组的特点,不难看出这是单调递增的, 所以我们猜想: 每一个单调队列中的决策点相对于后面的一段都有可能是最优决 策点,但是如何证明呢? 如果这个不是最优决策点,那么他后面的一段区间的最大值都与该点相等,而 f 非递增,所以决策都没有在单调队列中的决策好; 既然我们发现 f 与单调队列也有关系,那么此题单调队列的方向就已经确定; 维护上述的一个单调队列,在计算 f[i]时在单调队列中的所有点都有可能成为 决策点,对于这种情况可以用平衡树进行维护,但代码还有许多细节处理 #include<cstdio> #include<set> #include<iostream> using namespace std; const int mm=111111; int a[mm],q[mm],w[mm]; long long f[mm],sum,tmp,m; multiset<long long> sbt; int i,l,r,p,n; int main() { scanf("%d%lld",&n,&m); sbt.clear(); sum=l=0,f[n]=r=-1;

for(p=i=1;i<=n;++i) { scanf("%d%d",&a[i],&w[i]); sum+=w[i]; while(sum>m)sum-=w[p++]; while(l<=r&&a[i]>=a[q[r]]) { if(l<r)sbt.erase(f[q[r-1]]+a[q[r]]); --r; } q[++r]=i; if(l<r)sbt.insert(f[q[r-1]]+a[q[r]]); //手动 模拟下就会发现对于边界外决策点,其待定决策值为 f[q[i]-1]+a[q[i]]; while(q[l]<p) { if(l<r)sbt.erase(f[q[l]]+a[q[l+1]]); ++l; } f[i]=f[p-1]+a[q[l]]; 数组更新 tmp=*sbt.begin(); if(f[i]>tmp)f[i]=tmp; } cout<<f[n]; return 0; } //在 i 为当前最大值时用 p


推荐相关:

usaco bookshelf

usaco bookshelf_学科竞赛_高中教育_教育专区。usaco解题报告 1. 书架{bookshelf.pas/c/cpp} usaco2012 OpenGold usaco2012 Open Gold 【问题描述】 有 N(1 <=...


DP

Submatrix 2014 Tiling 2019 The Top Shelf 2044 Supermarket 2056 Bookshelf (*...硬币数不唯一 Dollars USACO Money Systems 1402 整数划分 不错 整数划分 的...

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