问一道题

给n个复数，如何从中选出一些，使得总和的模长最大？
n最大一百万，复数实、虚部为int范围。

apio上讲过...
如果知道最终和向量的方向...就好做了..直接取所有在该方向上射影为正的所有向量即可
那么扫描法逆时针扫描最终方向..维护选中的向量集合..在所有方向取取模长最大值就可以了..

我有个思路不知道对不对。。。
首先把向量按照与x轴夹角排序，那么选出的向量一定是连续的一段
然后DP，每次加进一个新向量t[i]时，比较以t[i-1]为尾的最优解+t[i]和t[i]的关系，如果前者大于后者那么t[i]的最优解为t[i-1]+t[i]，否则不断把t[i-1]首部的向量删除直到删完为止
自己yy的。。。估计是错的。。。

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

11回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六