干草堆tower

一个很好的dp.

显然最优的方案一定是最瘦的情况,从前往后是没有转移性质的,也不符合dp的最优解转移.

那么考虑从后往前转移,定义:

$f_{i}f\_i$表示到了第$ii$个的{最小宽度是多少,高度是多少},因为到了$ii$最小宽度的情况下,高度是最高的,顺带记录下高度即可.

转移很显然：

$f_i\mathrm{.}first=su{f}_i-su{f}_j,fi\mathrm{.}second=f_j\mathrm{.}second+1\{f\_i.first=suf\_i-suf\_j,fi.second=f\_j.second+1\}$。当$su{f}_i>=su{f}_j+f_j\mathrm{.}firstsuf\_i>=suf\_j+f\_j.first$。

由上面的贪心我们知道,$jj$越小越好.而且$f_j\mathrm{.}first+su{f}_{j}f\_j.first+suf\_j$一定是要递增的.不然单调性就不成立.

还有一个细节就是并不是你推进来就可以把前面所有比你小的全部删了,因为可能下一个的$su{f}_{i}suf\_i$不一定不小于当前的$su{f}_{now}+f_{now}suf\_\{now\}+f\_\{now\}$.所以我们要保留最后一个元素.

那么我们只要拿一个双端队列记录下转移就好了.

复杂度就可以到达$O(N)O(N)$.

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5+5;

int w[N],suf[N];
pair<int,int>f[N];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(int i=n;i>=1;i--)
		suf[i]=suf[i+1]+w[i];
	deque<int>q;
	int x=n+1;
	for(int i=n;i>=1;i--)
	{
		f[i]={suf[i],1};
		while(q.size()&&f[q.front()].first+suf[q.front()]<=suf[i])	
		{
			f[i].first=suf[i]-suf[q.front()],f[i].second=f[q.front()].second+1,x=q.front(),q.pop_front();
		}
		q.push_front(x);
		while(q.size()&&f[q.back()].first+suf[q.back()]>f[i].first+suf[i])	q.pop_back();
		q.push_back(i);
	}
	
	printf("%d\n",f[1].second);
	return 0;
}