题解：P10010 [集训队互测 2023] Grievous Lady

题目分析这道题一眼搜索或者动规，因为我看不出来怎么动规，所以准备用搜索解这道题。
题目做法 (1) 直接暴力搜索 (12pts) 我们将当作题目中，数组的长度，将当作搜索到哪一层了，这样我们便可以写出暴力代码： __int128 ans; __int128 x ,y; void dfs(int r,int c) { if(c==r+1) { __int128 s =x*y; if(s>ans) ans =s; return ; } x +=a[c].x; dfs(r,c+1); x -=a[c].x; y +=a[c].y; dfs(r,c+1); y -=a[c].y; } 此算法时间复杂度为让我们再看看数据范围，，这不得直接 T 飞？ (2) 整体贪心+局部搜索(100pts) 本蒟蒻也是看了第一篇题解才有的思路，我们发现，因为题目数据范围是随机的，并且值域非常大，所以和的值一般不会太接近，我们只需要取更大的那个数即可。但是这样做会有缺点，如果有和比较接近的情况出现，便很容易举出反例，这一部分我们就只能用搜索解决。于是，我们可以先将，数组以为排序标准进行降序排列，然后取正中间的个左右的断点进行枚举，先将断点左边大部分数和右边大部分数加入总数中，再暴力搜索断点附近的一些数更新答案就行了。求总和的代码大概是这样： void sum(int k) { x =0,y=0; //确定搜索范围 int l=max(1,k-5),r=min(n,k+5); //整体贪心 for(int i=1;i<l;i++) x +=a[i].x; for(int i=r+1;i<=n;i++) y +=a[i].y; //局部搜索 dfs(r,l); } 这样就可以将这道题切掉了。

文章操作