贪心（未完成）

我会带着你远行 2022-06-06 13:18 210阅读 0赞

数学公式：[http://blog.csdn.net/lanxuezaipiao/article/details/44341645][http_blog.csdn.net_lanxuezaipiao_article_details_44341645]  
下面的这些问题我都没打过，只有想过思路，可能会有错。

--------------------

P1325 雷达安装  
[https://www.luogu.org/problemnew/show/1325][https_www.luogu.org_problemnew_show_1325]

若竖直距离超过半径直接输出-1。  
预处理：以P为圆心，做半径为r的圆，交x轴于*q*1,*q*2，则若要覆盖这个点，雷达需在*q*1*q*2上。  
那么这一题就转化为线段覆盖问题了。对线段右端点进行排序，然后从右往左选取。

--------------------

P3146 \[USACO16OPEN\]248  
[https://www.luogu.org/problemnew/show/3146][https_www.luogu.org_problemnew_show_3146]  
给定一个1\*n的地图，在里面玩2048，每次可以合并相邻两个（数值范围1-40），问最大能合出多少。注意合并后的数值并非加倍而是+1，例如2与2合并后的数值为3。

我想到的：每一个联通块(大小大于1，假设为n,数值为i)合并后结果就是二进制下的1的个数个，其中最大的为i+最高二进制位对应的幂。  
比如：  
10(10)=1010(2)可以分出1\+*l**o**g*232和1\+*l**o**g*212。用树状数组的`x-=x&(-x)`每次取lowbit，就可以得到这个联通块合并出的结果了。  
那么贪心的策略就是每次对最小的非1联通块进行处理，记录并更新最值（取个max），两端如果存在x可以再次合并，就将其移动到x旁边。  
但是实现起来好像不太容易，而且感觉并不是最优的…  
看下题解发现是道DP题…那就重定向到DP专栏吧  
[http://blog.csdn.net/uiqrm/article/details/78313830][http_blog.csdn.net_uiqrm_article_details_78313830]

考虑用区间DP来解决。设dp\[i\]\[j\]表示区间i j所能获得的最大值。

[http_blog.csdn.net_lanxuezaipiao_article_details_44341645]: http://blog.csdn.net/lanxuezaipiao/article/details/44341645
[https_www.luogu.org_problemnew_show_1325]: https://www.luogu.org/problemnew/show/1325
[https_www.luogu.org_problemnew_show_3146]: https://www.luogu.org/problemnew/show/3146
[http_blog.csdn.net_uiqrm_article_details_78313830]: http://blog.csdn.net/uiqrm/article/details/78313830