蓝桥杯2018年第九届真题-倍数问题 DFS+神奇的优化

解题思路:
说明一下哪两个优化，首先我是先给数据从大到小排好序的，如果你在安排第二个数的时候你选择的第一个数还没有最大值的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;
}