首页 > 代码库 > 【BZOJ1560】【JSOI2009】火星藏宝图 [DP]
【BZOJ1560】【JSOI2009】火星藏宝图 [DP]
火星藏宝图
Time Limit: 10 Sec Memory Limit: 64 MB[Submit][Status][Discuss]
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
1<= M <=2000, 2<= N <=100000.
Main idea
每个点上有一个收益，从一个点走到另外一个点的花费是欧几里得距离的平方，问从(1,1)走到(m,m)的最大收益。
Solution
首先，运用DP。而且若A < C < B，显然则有 (A-B)^2 > (A-C)^2 + (C-B)^2。
那么我们对横坐标排序一下，可以保证横向的大小关系。然后对于一个转移，每一纵向只有最接近它的点有用。这样就可以做到O(nm)了。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 500005;12 const int INF = 2147483640;13 14 int n,m;15 int pos[ONE];16 int f[ONE];17 18 struct power19 {20 int x,y,z;21 }a[ONE];22 23 bool cmp(const power &a, const power &b)24 {25 if(a.x != b.x) return a.x < b.x;26 return a.y < b.y;27 }28 29 int cost(int Ax, int Ay, int Bx, int By)30 {31 return (Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By);32 }33 34 int get()35 { 36 int res=1,Q=1;char c; 37 while( (c=getchar())<48 || c>57 ) 38 if(c==‘-‘)Q=-1; 39 res=c-48; 40 while( (c=getchar())>=48 && c<=57 ) 41 res=res*10+c-48; 42 return res*Q;43 }44 45 int main()46 {47 n = get(); m = get();48 for(int i=1; i<=n; i++)49 a[i].x = get(), a[i].y = get(), a[i].z = get();50 sort(a+1, a+n+1, cmp);51 52 memset(f, -127, sizeof(f));53 pos[1] = 1; f[1] = 0;54 for(int id=1; id<=n; id++)55 {56 int x = a[id].x, y = a[id].y;57 int record = -INF;58 for(int j=1; j<=y; j++)59 if(pos[j])60 record = max( record, f[j] - cost(pos[j],j, x,y) );61 62 pos[y] = x;63 f[y] = record + a[id].z; 64 }65 66 printf("%d", f[m]);67 }68
【BZOJ1560】【JSOI2009】火星藏宝图 [DP]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。