问题描述&＃xff1a;
若有干个干草&＃xff0c; 分别有各自的宽度&＃xff0c; 要求将它们按顺序摆放&＃xff0c; 并且每层的宽度不大于 它的下面一层 &＃xff0c; 求最多叠几层
题解&＃xff1a;
zkw神牛证明了&＃xff1a; 底边最短&＃xff0c; 层数最高 证明&＃xff1a; 传送门
接下来我们就可以根据这个结论进行dp。 前缀和sum&＃xff0c; 以及 F[ i ]第 i 个数之后的干草叠起来后&＃xff0c; 底层的最短宽度&＃xff0c; 以及 H[ i ] 表示 第i个后的干草堆最高叠几层
有转移方程 : F[ i ] &＃61; min( sum[ j - 1] - sum[i - 1] ) ( j > i && sum[ j - 1] - sum[ i - 1] >&＃61; f[ j ] ) 由于前缀和从前往后是递增的&＃xff0c; 所以 j 越小越好。
又因为要满足 sum[ j - 1] - f[ j ] >&＃61; sum[ i - 1 ] &＃xff0c; 所以 sum[ j - 1] - f[ j ] 越大越好, 可以用单调队列来使决策具有单调性&＃xff0c; 每次取出队首就是最优决策
代码
1 #include
2 #include
3 #include
4 #define rd read()
5 #define rep(i,a,b) for( int i &＃61; (a); i <&＃61; (b); &＃43;&＃43;i )
6 #define per(i,a,b) for( int i &＃61; (a); i >&＃61; (b); --i )
7 using namespace std;
8
9 const int N &＃61; 1e5 &＃43; 1e4;
10
11 int n, a[N], sum[N], f[N], h[N], q[N];
12
13 int read() {
14 int X &＃61; 0, p &＃61; 1; char c &＃61; getchar();
15 for(; c > &＃39;9&＃39; || c <&＃39;0&＃39;; c &＃61; getchar() ) if( c &＃61;&＃61; &＃39;-&＃39; ) p &＃61; -1;
16 for(; c >&＃61; &＃39;0&＃39; && c <&＃61; &＃39;9&＃39;; c &＃61; getchar() ) X &＃61; X * 10 &＃43; c - &＃39;0&＃39;;
17 return X * p;
18 }
19
20 int main()
21 {
22 n &＃61; rd;
23 rep( i, 1, n ) sum[i] &＃61; sum[i - 1] &＃43; rd;
24 int l &＃61; 1, r &＃61; 1;
25 q[r] &＃61; n &＃43; 1;
26 sum[n &＃43; 1] &＃61; sum[n];
27 per( i, n, 1 ) {
28 while( l
29 f[i] &＃61; sum[ q[l] - 1] - sum[i - 1];
30 h[i] &＃61; h[q[l]] &＃43; 1;
31 while( l
32 q[&＃43;&＃43;r] &＃61; i;
33 }
34 printf("%d\n",h[1]);
35 }
京公网安备 11010802041100号