用了一个Meet-in-the-middle的技巧,还是第一次用到这个技巧,其实这个技巧和二分很像,主要是在dfs中,如果数量减小一半可以节约很多的时间。
Meet in the middle(有时候也叫作split and merge)是一种用以获取足够高效解决方案的灵巧的思想。和分治思想非常类似,它将问题分割成两个部分,然后试着合并这两个子问题的结果。好处在于通过使用一点额外的空间,你可以解决两倍规模的原来可以解决的问题。
#includeusing namespace std; typedef long long ll; set se[2]; const int maxn = 40; ll num[maxn]; ll n,m; void dfs(ll sum,ll l,ll r) { if(l == r) { se[r == n].insert(sum); return ; } dfs((sum+num[l])%m,l+1,r); dfs(sum,l+1,r); } int main() { scanf("%lld%lld",&n,&m); for(int i=0;i ::iterator iter,iter2; ll Max = 0; for(iter=se[0].begin();iter!=se[0].end();iter++) { ll x = *iter; ll y = m - 1 - x; iter2 = se[1].upper_bound(y); iter2--; Max = max(Max,(x+*iter2)%m); } printf("%lld",Max); }