(原题传送门) https://www.luogu.org/problemnew/show/P2038
思路
蒟蒻看到这道题的数据范围后表示瑟瑟发抖, 然而敲完 LowLow 的 Code 后发现竟然 AC 了?!! 好吧, 这道题的数据范围就是唬人的, 拿出草纸计算一下就能发现 O(n4) 的时间复杂度就能 AC, 本蒟蒻脑容量有限, 表示想不出来也看不懂 O(n2) 的算法, A 完 C 就跑~~~.
这道题为了数组不越界, 产生负下标, 可以通过特判来解决, 但本蒟蒻采用了更暴力的做法: 直接从 cross[21][21] 开始存储 (n<=20), 把没用到的空间置 0, 这样如果访问小于 21 的下标能得到也不过就是 0(天才构思, 快鼓掌).
然后, 用一个 2 重循环来尝试每一个可能的选址, 再嵌套一个二重循环来计算每个选址的 "价值", 然后将其与最大值比较, 若等于最大值, 那么说明最大的选址方案多了一种, 将记录最大选址方案数的变量 sum++, 若大于最大值, 说明之前所有的最大方案都是假的, 存在更大的, 将 sum 归 1, 并将最大值设置为目前值.
最后, 输出即可.
剩下的就是水代码了 QAQ.
- Code
- #include<iostream>
- using namespace std;
- int x,y,d,n,gkmax,num,sum=1,cross[170][170];
- int main()
- {
- cin>>d>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>x>>y>>cross[x+20][y+20];
- }
- for(int i=20;i<=148;i++)
- for(int j=20;j<=148;j++)
- {
- for(int m=i-d;m<=i+d;m++)
- for(int k=j-d;k<=j+d;k++)
- num+=cross[m][k];
- if(gkmax==num)
- {
- sum++;
- }
- if(gkmax<num)
- {
- sum=1;
- }
- gkmax=max(gkmax,num);
- num=0;
- }
- cout<<sum<<" "<<gkmax;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3092788.html