公司网站备案需要哪些资料,河北网站备案,无锡网站优化推广方案,哪些公司用.cc做网站P5095 [USACO12OPEN] Bookshelf S 文章目录 P5095 [USACO12OPEN] Bookshelf S题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路赛时 code别人code 题目描述
Farmer John 闲来无事的时候总喜欢坐下来看书。这些年来#xff0c;他一共收集了 N N N 本书#…P5095 [USACO12OPEN] Bookshelf S 文章目录 P5095 [USACO12OPEN] Bookshelf S题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示思路赛时 code别人code 题目描述
Farmer John 闲来无事的时候总喜欢坐下来看书。这些年来他一共收集了 N N N 本书 1 ≤ N ≤ 2000 1 \leq N \leq 2000 1≤N≤2000他打算搭一共新的书架来装这些书。
每本书都有个宽度 w i w_i wi 和高度 h i h_i hi书必须按顺序来摆放即同一层书架摆的书必须是连续的一个区间。每层书架的总宽度不能超过 L L L 1 ≤ L ≤ 1 0 9 1 \leq L \leq 10^9 1≤L≤109每层书架的高度等于这一层最高的书的高度整个书架的高度等于每层书架的高度之和。
现在请你帮 FJ 求出书架高度的最小值。
输入格式
第一行两个整数 N , L N,L N,L。
接下来 N N N 行每行两个整数 h i , w i h_i,w_i hi,wi 1 ≤ h i ≤ 1 0 6 1 \leq h_i \leq 10^6 1≤hi≤106 1 ≤ w i ≤ L 1 \leq w_i \leq L 1≤wi≤L。
输出格式
输出一个整数书架高度最小值。
样例 #1
样例输入 #1
5 10
5 7
9 2
8 5
13 2
3 8样例输出 #1
21提示
第一层放第一本书第二层放第二三四本书第三层放第五本书总高度为 5 13 3 21 513321 513321可以证明不存在更优的方案。
思路
盲猜dp
一开始是两重的数组要用线段树和 r m q rmq rmq 维护还不能过。
后面发现其实最终的层数和答案关系不大关键的是高度
所以我们设 d p i dp_i dpi 表示放下前 i i i 本书的最小高度
那么 d p i M I N j 1 i − 1 d p j M A X k j i h k dp_i MIN_{j 1}^{i - 1} dp_j MAX_{k j}^ih_k dpiMINj1i−1dpjMAXkjihk 考试时我用了 r m q rmq rmq 维护后面的 h h h 其实不用只要 j j j 从后枚举维护最大值就好了。
赛时 code
#include bits/stdc.h
#define fu(x , y , z) for(int x y ; x z ; x )
#define fd(x , y , z) for(int x y ; x z ; x --)
#define LL long long
using namespace std;
const int N 2005;
LL l , h[N] , w[N] , sq[35] , rmq[N][35] , ans , s[N] , dp[N];
int n;
void pre () {sq[0] 1;for (int i 1 ; i 30 ; i ) sq[i] sq[i - 1] * 2;fu (i , 1 , n) rmq[i][0] h[i];fu (j , 1 , 30) {fu (i , 1 , n) {if (i sq[j] - 1 n) break;rmq[i][j] max (rmq[i][j - 1] , rmq[i sq[j - 1]][j - 1]);}}
}
LL find (int x , int y) {int lst 30 , z;LL ansf 0;while (x y) {for (int i lst ; i 0 ; i --) {if (x sq[i] - 1 y) continue;ansf max (ansf , rmq[x][i]);x x sq[i];z i;}lst z;}ansf max (ansf , h[y]);return ansf;
}
int main () {scanf (%d%lld , n , l);fu (i , 1 , n)scanf (%lld%lld , h[i] , w[i]);pre ();fu (i , 1 , n) s[i] s[i - 1] w[i];fu (i , 1 , n) dp[i] 1e18 5;fu (i , 1 , n) {fd (j , i - 1 , 0) {if (s[i] - s[j] l) break;dp[i] min (dp[i] , dp[j] find (j 1 , i));}}printf (%lld , dp[n]);return 0;
}别人code
#include bits/stdc.h
using namespace std;
const int N 2002;
int n, m, p, k, ans, sum, tot, cnt, a[N], b[N], f[N], c[N], l;
int main()
{std::cin n l;for(int i 1; i n; i){std::cin a[i] b[i];c[i] c[i - 1] b[i];f[i] 1e9;}for(int i 1; i n; i){f[i] f[i - 1] a[i];tot a[i];for(int j i - 1; j 1; j--){if(c[i] - c[j - 1] l)break;tot max(tot, a[j]);f[i] min(f[i], f[j - 1] tot);}}cout f[n];return 0;
}
