生活随笔
收集整理的这篇文章主要介绍了
HDU6638 Snowy Smile
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
http://acm.hdu.edu.cn/showproblem.php?pid=6638
题意：平面上有n个带权点，问用一个矩形围住的所有点权和最大是多少？
思路：把y坐标离散化，然后按x排序，枚举右边界，依次一列一列地加点，依次求最大子段和。
复杂度O(n∗nlog(n))O(n*nlog(n))O(n∗nlog(n))
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=2010;
typedef long long ll
;int T
,n
;
struct Point
{int x
,y
,w
;bool operator < (Point z
){return x
>z
.x
;}
}p
[maxn
];ll lmax
[maxn
*4],rmax
[maxn
*4],maxx
[maxn
*4],sumv
[maxn
*4];void build()
{memset(lmax
,0,sizeof(lmax
));memset(rmax
,0,sizeof(rmax
));memset(maxx
,0,sizeof(maxx
));memset(sumv
,0,sizeof(sumv
));
}void maintain(int o
)
{int lc
=o
*2,rc
=o
*2+1;sumv
[o
]=sumv
[lc
]+sumv
[rc
];maxx
[o
]=max(maxx
[lc
],maxx
[rc
]);maxx
[o
]=max(maxx
[o
],rmax
[lc
]+lmax
[rc
]);lmax
[o
]=max(lmax
[lc
],sumv
[lc
]+lmax
[rc
]);rmax
[o
]=max(rmax
[rc
],sumv
[rc
]+rmax
[lc
]);
}void update(int o
,int l
,int r
,int p
,int v
)
{if(l
==r
){sumv
[o
]+=v
;lmax
[o
]+=v
;rmax
[o
]+=v
;maxx
[o
]+=v
;}else{int m
=(l
+r
)/2;if(p
<=m
)update(o
*2,l
,m
,p
,v
);else update(o
*2+1,m
+1,r
,p
,v
);maintain(o
);}
}int main()
{cin
>>T
;while(T
--){cin
>>n
;vector
<int> v
;for(int i
=1;i
<=n
;i
++){scanf("%d%d%d",&p
[i
].x
,&p
[i
].y
,&p
[i
].w
);v
.push_back(p
[i
].y
);}sort(v
.begin(),v
.end());v
.erase(unique(v
.begin(),v
.end()),v
.end());int sz
=v
.size();for(int i
=1;i
<=n
;i
++)p
[i
].y
=lower_bound(v
.begin(),v
.end(),p
[i
].y
)-v
.begin()+1;sort(p
+1,p
+1+n
);ll ans
=0; for(int i
=1;i
<=n
;i
++){if(i
!=1&&p
[i
].x
==p
[i
-1].x
)continue;build();int j
=i
,start
=i
;while(j
<=n
){while(j
<=n
){if(j
!=start
&& p
[j
].x
!=p
[j
-1].x
)break;update(1,1,n
,p
[j
].y
,p
[j
].w
);j
++;}ans
=max(ans
,maxx
[1]);start
=j
;}}cout
<<ans
<<endl
;}return 0;
}
总结
以上是生活随笔为你收集整理的HDU6638 Snowy Smile的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
