首页 > 代码库 > bzoj1233: [Usaco2009Open]干草堆tower 单调队列优化dp
bzoj1233: [Usaco2009Open]干草堆tower 单调队列优化dp
又是一道单调队列优化dp的题目 这道题呢 先要了解一个结论,在多种可行的堆叠方案中,至少有一种能使层数最高的方案同时使得底边最短。即底边最短的,层数一定最高。 这个是zkw大神得出的 我也不会证明来着 反正这样之后我们就可以得出正确的方法了
递推式 F[i]=min(sum[j-1]-sum[i-1]) j>i 且 sum[j-1]-sum[i-1]>=F[j] 易得在满足的条件下j当然是越小越好了嘛 而这样得出的方程又满足一定的单调性 这样调整之后队首就是我们要的答案啦
又对于转移条件 f[j]<=sum[j?1]?sum[i?1]f[j]<=sum[j?1]?sum[i?1] 我们把式子移项得到 sum[i?1]<=sum[j?1]?f[j] 所以若k>j且sum【k-1】-f【k】>=sum【j-1】-f【j】那k一定不是最优解就可以舍弃啦
剩下的看看代码吧
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=100007; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int f[M],g[M],sum[M],q[M],head,tail,n,w; int main() { n=read(); for(int i=1;i<=n;i++) w=read(),sum[i]=sum[i-1]+w; q[0]=n+1; for(int i=n;i;i--){ while(head<tail&&sum[q[head+1]-1]-sum[i-1]>=f[q[head+1]]) head++; f[i]=sum[q[head]-1]-sum[i-1]; g[i]=g[q[head]]+1; while(head<tail&&f[i]-sum[i-1]<=f[q[tail]]-sum[q[tail]-1]) tail--; q[++tail]=i; } printf("%d\n",g[1]); return 0; }
bzoj1233: [Usaco2009Open]干草堆tower 单调队列优化dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。