首页 > 代码库 > BZOJ 1560 火星藏宝图（DP）
BZOJ 1560 火星藏宝图（DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1560
题意：
思路：f[i]表示到达i的最大收益。这样是 O(n^2)的。我们考虑，由于转移的条件，a^2+b^2<(a+b)^2，因此对于三个点A、B、C。若A能到B，B能到C，那么A也能到C， 但是不如经过B更好。因此，我们记录到达第j列最靠下的i即可。那么转移(x,y)时，用记录的前y列即可。
struct node{ int x,y,w;};node a[N];int b[1005],c[1005],n,m;int cmp(node a,node b){ if(a.x!=b.x) return a.x<b.x; return a.y<b.y;}int dis(int x1,int y1,int x2,int y2){ return sqr(x1-x2)+sqr(y1-y2);}int main(){ RD(n,m); int i,j; FOR1(i,n) RD(a[i].x,a[i].y,a[i].w); sort(a+1,a+n+1,cmp); int x,y,w,temp; FOR1(i,m) b[i]=-INF; b[1]=a[1].w; c[1]=1; for(i=2;i<=n;i++) { x=a[i].x; y=a[i].y; w=a[i].w; temp=-INF; for(j=1;j<=y;j++) upMax(temp,b[j]-dis(x,y,c[j],j)); temp+=w; b[y]=temp; c[y]=x; } PR(temp);}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。