【BZOJ4654】【NOI2016】国王饮水记
首先目测一下。。如果没有次数使用限制怎么搞最好? 首先比\(1\)号城市水箱低的没什么用,不但没贡献还会把别的 … 阅读更多【BZOJ4654】【NOI2016】国王饮水记
Welcome to XuYike's Weblog
首先目测一下。。如果没有次数使用限制怎么搞最好? 首先比\(1\)号城市水箱低的没什么用,不但没贡献还会把别的 … 阅读更多【BZOJ4654】【NOI2016】国王饮水记
我弃疗好吗。。 首先\(dp_i=min(dp_j+p_i(dis_i-dis_j))+q_i\) 首先如果它 … 阅读更多【BZOJ3672】【NOI2014】购票
题意:给定一个\(m\times m\)的网格和\(n\)个其中的关键点,用不超过\(k\)个中心在网格主对角 … 阅读更多【IOI2016】外星人
可以首先得到一个结论:一个序列的划分位置如果确定,那么结果就是确定的,与划分顺序无关 于是很容易想到dp,令\ … 阅读更多【BZOJ3675】【APIO2014】序列分割
斜率优化水题 不开long long简直制杖
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
// <1597.cpp> - 07/19/16 20:00:09 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=50010; const int INF=1e9; struct land{ int x,y; bool operator <(const land b) const{return x==b.x?y<b.y:x<b.x;} }a[MAXN]; lol dp[MAXN]; #define k(u,v) double(dp[v-1]-dp[u-1])/(a[v].y-a[u].y) int q[MAXN]; bool v[MAXN]; int main(){ int n=gi(); for(int i=1;i<=n;i++)a[i].x=gi(),a[i].y=gi(); sort(a+1,a+n+1); int maxy=0; for(int i=n;i;i--) if(a[i].y>maxy)v[i]=1,maxy=max(maxy,a[i].y); int t=0; for(int i=1;i<=n;i++)if(v[i])a[++t]=a[i]; n=t; int l=1,r=0; for(int i=1;i<=n;i++){ while(l<r&&k(q[r-1],q[r])<=k(q[r],i))r--; q[++r]=i; while(l<r&&k(q[l],q[l+1])>=-a[i].x)l++; dp[i]=dp[q[l]-1]+1ll*a[i].x*a[q[l]].y; } printf("%lld",dp[n]); return 0; } |
居然又是斜率优化。。 总结出一些规律:凡是看起来sb的dp复杂度又不对的就是斜率优化。。当然一般是区间这样的问 … 阅读更多【BZOJ1096】【ZJOI2007】仓库建设
已经有感觉了诶。。一眼秒出是斜率优化 因为修正战斗力是个二次函数并且开口向下,显然如果对于一个点x而言,l&l … 阅读更多【BZOJ1911】【APIO2010】特别行动队
AC数rank 3 感觉这题就是个**dp 想着赶快切了这道题的 \(dp_i\)表示以i为结尾的答案那么 $ … 阅读更多【BZOJ1010】【HNOI2008】玩具装箱