解题思路:
说明一下哪两个优化,首先我是先给数据从大到小排好序的,如果你在安排第二个数的时候你选择的第一个数还没有最大值的1/3大,你后面选择的两个数必定小于第一个数,因此不可能超过最大值,直接回溯,两个优化都是这个思想。
注意事项:
参考代码:
#include#includeusing namespace std; int a[100010]; int n,k; bool vis[100010]; int cnt; void dfs(int x,int sum){ if(x>=4){ if(sum%k==0) cnt = max(cnt,sum); return; } if(x==3&&sum<cnt*2/3) //优化前36 优化后66 相当于减去挑选第二个数时很小的情况 return; if(x==2&&sum=0;i--){ if(!vis[i]){ vis[i] = true; dfs(x+1,sum+a[i]); vis[i] = false; } } } int main(){ cin>>n>>k; for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); dfs(1,0); cout<<cnt; return 0; }
0.0分
4 人评分
C语言程序设计教程(第三版)课后习题8.8 (C++代码)浏览:542 |
The 3n + 1 problem (C语言代码)浏览:1339 |
化学品问题 (C语言代码)浏览:1330 |
C语言训练-字符串正反连接 (C语言代码)浏览:690 |
C语言训练-谁家孩子跑最慢* (C语言代码)浏览:1507 |
C语言训练-求1+2!+3!+...+N!的和 (C语言代码)浏览:2468 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:967 |
矩形面积交 (Java代码)浏览:1213 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:659 |
淘淘的名单 (C语言代码)答案错误???浏览:593 |
flags 2021-04-13 17:12:21 |
我加了解释你可以看看