同样是一个斜率优化，设f[i]表示在i处建仓库，f[i] = f[j] + cal(j,i) + c[i];
一开始cal想了我好久，一直只想到o（n）cal。。。
后面看着花花想cal的实现，一下子就想出来了！！！
斜率优化的一般方法应该是 f[i] + 只与i有关的看作c，只与j有关的看作by，与ij有关的j看作x，i看作a，再用向量积去做
等下再用决策单调性优化写下这道题。。
妈蛋一开始队列写错了卡了15分钟！！！最近老是犯些SB错误。。还是静不下来啊
1 /* 2 ID:WULALA 3 PROB:bzoj1096_slope 4 LANG:C++ 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <algorithm> 9 #include <cmath> 10 #include <iostream> 11 #include <ctime> 12 #include <set> 13 #define N 1000008 14 #define M 15 #define mod 16 #define mid(l,r) ((l+r) >> 1) 17 #define INF 0x7ffffff 18 using namespace std; 19 20 long long l,r,n,p[N],que[N],f[N],d[N],c[N],s[N],sum[N]; 21 22 void init() 23 { 24 scanf("%lld",&n); 25 for (int i = 1;i <= n;i++) 26 { 27 scanf("%lld%lld%lld",&d[i],&p[i],&c[i]); 28 s[i] = s[i-1] + sum[i-1] * (d[i] - d[i-1]); 29 sum[i] = sum[i-1] + p[i]; 30 } 31 l = r = 1; 32 } 33 34 long long cal(long long x,long long y) 35 { 36 long long r = (f[x] + s[y] - s[x] - sum[x] * (d[y] - d[x]) + c[y]); 37 return r; 38 } 39 40 long long cross(long long o,long long a,long long b) 41 { 42 long long xo = sum[o],yo = f[o] - s[o] + sum[o] * d[o]; 43 long long xa = sum[a],ya = f[a] - s[a] + sum[a] * d[a]; 44 long long xb = sum[b],yb = f[b] - s[b] + sum[b] * d[b]; 45 xa -= xo; ya -= yo; 46 xb -= xo; yb -= yo; 47 return (xa * yb - xb * ya); 48 } 49 50 void debug(long long a) 51 { 52 printf("%lld %lld\n",que[l],f[a]); 53 } 54 55 int main() 56 { 57 init(); 58 for (int i = 1;i <= n;i++) 59 { 60 while (l < r && cal(que[l],i) > cal(que[l+1],i)) 61 l++; 62 f[i] = cal(que[l],i); 63 // debug(i); 64 while (l < r && cross(que[r-1],que[r],i) < 0) r--; 65 que[++r] = i; 66 } 67 printf("%lld\n",f[n]); 68 return 0; 69 }
决策单调性
1 /* 2 ID:WULALA 3 PROB:bzoj1096_mono 4 LANG:C++ 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <algorithm> 9 #include <cmath> 10 #include <iostream> 11 #include <ctime> 12 #include <set> 13 #define N 1000008 14 #define M 15 #define mod 16 #define mid(l,r) ((l+r) >> 1) 17 #define INF 0x7ffffff 18 using namespace std; 19 20 long long l,r,n,p[N],que[N],f[N],d[N],c[N],s[N],sum[N],st[N]; 21 22 void init() 23 { 24 scanf("%lld",&n); 25 for (int i = 1;i <= n;i++) 26 { 27 scanf("%lld%lld%lld",&d[i],&p[i],&c[i]); 28 s[i] = s[i-1] + sum[i-1] * (d[i] - d[i-1]); 29 sum[i] = sum[i-1] + p[i]; 30 } 31 for (int i = 1;i <= n+1;i++) st[i] = n + 1; 32 l = r = 1; st[0] = 1; 33 } 34 35 long long cal(long long x,long long y) 36 { 37 long long r = (f[x] + s[y] - s[x] - sum[x] * (d[y] - d[x]) + c[y]); 38 return r; 39 } 40 41 long long find(long long a) 42 { 43 long long top = r + 1,bot = l;//top应= r + 1;!! 44 while (bot != top) 45 { 46 if (st[que[mid(bot,top)]] <= a) bot = mid(bot,top) + 1; 47 else top = mid(bot,top); 48 } 49 return (bot - 1); 50 } 51 52 int main() 53 { 54 init(); 55 for (int i = 1;i <= n;i++) 56 { 57 f[i] = cal(que[find(i)],i); 58 while (r && cal(que[r],st[que[r]]) > cal(i,st[que[r]])) r--; 59 int bot = st[que[r]],top = n + 1; 60 while (bot != top) 61 { 62 if (cal(que[r],mid(top,bot)) > cal(i,mid(top,bot))) top = mid(top,bot); 63 else bot = mid(top,bot) + 1; 64 } 65 if (bot == n + 1) continue; 66 que[++r] = i; 67 st[i] = bot; 68 } 69 printf("%lld\n",f[n]); 70 return 0; 71 }
感觉斜率优化式子写出来以后比决策单调性还好写些（>__<）