給一個數列和m，在數列任選若干個數，使得他們的和對m取模后最大（ \(1<=n<=35\) , \(1<=m<=10^{9}\)）

考慮把數列分成兩份，兩邊分別暴力求出所有的可能，那么對于一個數列中每一個數字\(x\)，另一個數列加上它之后小于\(m\)的那個數是最優的，用雙指針可以做到\(O(2^{n/2})\)

如果最終的答案是兩個數列中的數加起來且大于\(m\)的，因為所有可能都是在模意義下，所以肯定是兩個數列中最大的數加起來最優，判斷一下就好了

//minamoto #include<bits/stdc++.h> #define R register #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R int x){if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;while(z[++Z]=x%10+48,x/=10);while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=(1<<18)+5; int n,P,lim,f[N],g[N],a[55],tf,tg,ans; inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;} void dfs1(int pos,int lim,int res){if(pos==lim)return (void)(f[++tf]=res,f[++tf]=add(res,a[pos]));dfs1(pos+1,lim,res),dfs1(pos+1,lim,add(res,a[pos])); } void dfs2(int pos,int lim,int res){if(pos==lim)return (void)(g[++tg]=res,g[++tg]=add(res,a[pos]));dfs2(pos+1,lim,res),dfs2(pos+1,lim,add(res,a[pos])); } int main(){ // freopen("testdata.in","r",stdin);n=read(),P=read(),lim=n>>1;fp(i,1,n)a[i]=read()%P;if(n==1)return printf("%d\n",a[1]),0;dfs1(1,lim,0),dfs2(lim+1,n,0);sort(f+1,f+1+tf),sort(g+1,g+1+tg);for(R int i=1,j=tg;i<=tf;++i){while(f[i]+g[j]>=P)--j;cmax(ans,f[i]+g[j]);}cmax(ans,f[tf]+g[tg]-P); printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10217963.html

總結

以上是生活随笔為你收集整理的CF888E Maximum Subsequence（meet in the middle）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。