bzoj1560：[JSOI2009]火星藏宝图（斜率优化）

题目描述

在火星游玩多日,jyy偶然地发现了一张藏宝图。根据藏宝图上说法，宝藏被埋藏在一个巨大的湖里的N个岛上(2<=N<=200,000)。为了方便描述，地图把整个湖划分成M行M列(1<=M<=1000),共M*M个小块，并把所有岛按照1...N编了号。第i个岛位于第Xi行Yi列（设其坐标为(Xi,Yi))的格子(Xi,Yi均为整数，并且满足1<=Xi,Yi<=M),岛上藏有价值财富Vi(1<=Vi<=10,000)。湖的左上角(1,1)和右下角(M,M)都有岛，有桥将它们与陆地相连。

jyy没费多大劲，就找到了那个湖，同时哭笑不得地发现，所谓的财富，是各个岛上出产的珍稀水果。jyy 在左上角的岛的岸边找到了一条小木船，他可以划船到其他岛上去。划船是要消耗体力的，具体地说，等于两岛 Euclidean 距离的平方(即，从(X1,Y1)划船到(X2,Y2)所耗费的体力为(X1-X2)^2+(Y1-Y2)^2个单位)。jyy可以吃水果来恢复体力，吃掉1单位价值的水果能恢复1单位体力。

现在jyy打算从(1,1)旅行到(M,M)，沿途收集珍稀水果。按藏宝图上的提示，jyy 离开一个岛后，就只能去该岛右下方的区域（正下和正右方向也是允许的），否则会遭遇水怪。jyy可以在旅行途中饿一段时间，即体力为负。但抵达终点后，只要身边有足够多的水果，他就会通过吃水果将体力恢复到旅行前的水平。

jyy想知道，经过一次旅行，他最多能得到多少收益，即jyy收集到的水果总价值-jyy在旅途中花的总体力。(如果吃完所有水果他还饿着，收益就是负数，具体的例子见样例)

输入输出格式

输入格式：

第1行：两个整数N,M。第2..N+1行：每行3个整数，第i+1行的3个整数分别为Xi，Yi，Vi。每个岛的坐标不同。保证存在坐标(1,1)和(M,M)的岛。

输出格式：

第1行：输出一个整数，表示最大收益。

输入输出样例

输入样例#1：复制

输出样例#1：复制

-4

说明

20+60+10-((3-1)^2+(5-1)^2)-((10-3)^2+(10-5)^2)=-4

对20%的数据M<=200，且N<=2,000

对50%的数据M<=200，且N<=20,000

对100%的数据M<=1000，且N<=200,000

题解

　　话说斜率优化的题解好玄学orz->这里

　　考虑$dp_i$为走到$i$点的最大收益，则转移方程为$dp_i=max\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+w_i$

　　如果直接转移的话是$O(n^2)$的，然而这里有一个特性，同一列中能转移的点肯定是行数大的更优

　　为啥咧？从行数小的点先走到行数大的再走到该点在竖直方向上花费为$a^2+b^2$，直接走到该点在竖直方向上的花费为$(a+b)^2$，他们水平方向上的花费一样，那么肯定先走到行数大的点的花费会更小

　　然后据说这样就能用$O(nm)$卡过去了

　　然而这和斜率优化有什么关系么？（没有）

　　设$dp_{i,j}$表示走到$(i,j)$的最大收益，我们可以枚举从哪一列转移到这里。因为只要确定了列就可以确定行，我们设$pos_i$表示第$i$列能转移点的最大行数，$x$为当前点行数，省略$dp$数组的第一维，设$dis_j=(x-pos_j)^2$，则有$$dp_i=max\{dp_j-dis_j-(i-j)^2+w_{x,i}\}$$

　　设$j<k$且从$k$转移比从$j$转移更优，则有$$dp_j-dis_j-(i-j)^2<dp_k-dis_k-(i-k)^2$$

　　$$dp_i-dp_k-dis_j+dis_k-j^2+k^2<2*i*(k-j)$$

　　$$\frac{dp_i-dp_k-dis_j+dis_k-j^2+k^2}{(k-j)*2}<i$$

　　然后就可以斜率优化了……虽然基本都是抄的但还是累死我了……

　　顺便注意如果$j=k$的时候斜率返回$inf$或$-inf$

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,inf=0x3f3f3f3f;

 int n,m,h,t,x,y,q[N];

 int dp[N][N],w[N][N],pos[N],dis[N];

 inline double slope(int x,int y){

     return x==y?-inf:1.0*(dp[pos[x]][x]-dp[pos[y]][y]-dis[x]+dis[y]-x*x+y*y)//(y-x);

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read(),m=read();

     for(int i=;i<=n;++i) x=read(),y=read(),w[x][y]=read();

     memset(dp,0xef,sizeof(dp));

     dp[][]=w[][],pos[]=,w[][]=;

     for(int i=;i<=m;++i){

         for(int j=;j<=m;++j) dis[j]=(pos[j]!=)*(pos[j]-i)*(pos[j]-i);

         h=,t=;

         for(int j=;j<=m;++j){

             if(pos[j]){

                 while(h<t&&slope(q[t-],q[t])>slope(q[t],j)) --t;

                 q[++t]=j;

             }

             if(w[i][j]){

                 while(h<t&&slope(q[h],q[h+])<j) ++h;

                 dp[i][j]=dp[pos[q[h]]][q[h]]-dis[q[h]]-(q[h]-j)*(q[h]-j)+w[i][j];

                 pos[j]=i,dis[j]=;

                 while(h<t&&slope(q[t],q[t-])>slope(q[t],j)) --t;

                 q[++t]=j;

             }

         }

     }

     printf("%d\n",dp[m][m]);

     return ;

 }

巴特西

bzoj1560：[JSOI2009]火星藏宝图（斜率优化）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章