BZOJ 1560: [JSOI2009]火星藏宝图
正文索引 [隐藏]
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1560
Description
Input
Output
Sample Input
4 10
1 1 20
10 10 10
3 5 60
5 3 30
1 1 20
10 10 10
3 5 60
5 3 30
Sample Output
-4
HINT
题解
首先我们明确一点，从 (0,0) 移动到 (x,y) ，假定 x1+x2=x && y1+y2=y 。如果直接从(0,0)移动到(x,y)，那么花费为x^2+y^2=x1^2+x2^2+2x1x2+y1^2+y2^2+2y1y2 > x1^2+y1^2+x2^2+y2^2 ，所以同样位置的移动，中继点越多花费越少。
那么很明显，我们要尽量多走一些点。
我们把点全部记录，并且按照行优先列其次的顺序排序，这样保证顺序做的时候与行。
然后，我们记F[j]为1~当前行，第j列最下面的岛屿的最优值。 O(M)转移，所以总的复杂度是O(MN)
不知道为什么，别人快得飞起，我却要开读入挂才能过。
代码
|
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 51 52 53 54 55 56 57 58 59 60 61 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const long long Inf=2100000000; const int Maxn=2e5; const int Maxm=1e3; struct LandNode{ int x,y; int val; }; LandNode land[Maxn+50]; inline bool cmpLand(LandNode a,LandNode b){ if (a.x!=b.x) return a.x<b.x; return a.y<b.y; } int n,m; long long F[Maxm+50]; int last[Maxm+50]; inline long long sqr(int x){ return (long long)x*(long long)x; } inline void read(int &num){ num=0; char x=getchar(); while(!('0'<=x && x<='9')) x=getchar(); do{ num=num*10+(x-'0'); x=getchar(); }while('0'<=x && x<='9'); } inline void solve(){ //memset(F,0,sizeof(F)); for (int i=1;i<=n;i++){ read(land[i].x); read(land[i].y); read(land[i].val); } sort(land+1,land+n+1,cmpLand); //memset(last,0,sizeof(last)); last[1]=1; F[1]=land[1].val; //for (int i=1;i<=n;i++) printf("%d %d %dn",land[i].x,land[i].y,land[i].val); for (int i=2;i<=n;i++){ long long now=-Inf; for (int c=1;c<=land[i].y;c++){ if (last[c]!=0) now = max(now, F[c] - sqr(land[i].x-land[last[c]].x) - sqr(land[i].y-land[last[c]].y) ); } last[land[i].y]=i; F[land[i].y]=now+(long long)land[i].val; //printf("# %d -> %lldn",i,now); //for (int i=1;i<=m;i++) printf("F[%d]=%lldn",i,F[i]); } printf("%lldn",F[m]); } int main(){ while(scanf("%d%d",&n,&m)!=EOF) solve(); return 0; } |
原文链接：BZOJ 1560: [JSOI2009]火星藏宝图
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!