BZOJ 1560 JSOI2009 火星藏宝图 动态规划
浏览数：41 /
时间：2015年06月09日
题目大意：给定一个m*m的矩阵，上面有n个点，每个点上有一个正的收益，在两个点之间走的代价是距离的平方，求(1,1)到(m,m)的最大收益
直接排序并且DP的方法很容易想到 但是显然O(n^2)过不去
考虑平方的特性 由于A和B都大于等于0时(A+B)^2>=A^2+B^2 因此A->B->C一定比A->C更优
根据这个特性，我们可以将点按照纵坐标为第一键值，横坐标为第二键值排序
对于每一列我们维护一个当前纵坐标最大的点 用这个点更新一定比它下面的点更新更优
因此对于每个点枚举横坐标比它小的列更新即可 时间复杂度O(nm) 大概2E左右
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct Point{
int x,y,z,f;
friend istream& operator >> (istream& _,Point &p)
{
scanf("%d%d%d",&p.x,&p.y,&p.z);
p.f=-INF;
return _;
}
bool operator < (const Point &p) const
{
if(y!=p.y)
return y<p.y;
return x<p.x;
}
friend int Distance(const Point &p1,const Point &p2)
{
return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
void Update(const Point &p)
{
f=max(f,p.f-Distance(p,*this)+z);
}
}points[200200];
int n,m;
Point *now[1010];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1560.in","r",stdin);
#endif
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
cin>>points[i];
sort(points+1,points+n+1);
points[1].f=points[1].z;
for(i=1;i<=n;i++)
{
for(j=1;j<=points[i].x;j++)
if(now[j])
points[i].Update(*now[j]);
now[j-1]=&points[i];
}
cout<<points[n].f<<endl;
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
