[CodeForces 888E] Maximum Subsequence

CodeForces 888E

分类

枚举,折半

大意:

给你最多35个整数, 选出一个子集使得这个子集的和取余m最大,求最大的余数

时空限制:

1000ms/262144kB

输入格式:

第1行2个整数n,m

第2行n个整数

输出格式:

1行1个整数,表示最大的余数

数据范围:

1<=n<=35,1<=m<=10⁹

---

折半枚举
将数列从中间分成两部分
前一部分用O(2^n/2)的复杂度算出每个子集除m的余数,更新Max之后存起来(用set比较方便)
后部分同样算出余数,更新Max之后从前半部分寻找对应加起来除m余数最大的部分加起来更新Max

#include<bits/stdc++.h>
using namespace std;
int n,m,Max;
int a[36];
set<int>s;
void dfs1(int l,int sum){
	if(l==n/2+1){
		Max=max(Max,sum);
		s.insert(sum);
		return;
	}
	dfs1(l+1,(sum+a[l])%m);
	dfs1(l+1,sum);
}
void dfs2(int l,int sum){
	if(l==n+1){
		Max=max(Max,sum);
		set<int>::iterator it=s.lower_bound(m-sum);
		if(it!=s.begin()){
			it--;
			Max=max(Max,(*it)+sum);
		}
		return;
	}
	dfs2(l+1,(sum+a[l])%m);
	dfs2(l+1,sum);
} 
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dfs1(1,0);
	dfs2(n/2+1,0);
	printf("%d\n",Max);
    return 0;
}