0x22 迭代加深-白红宇

0x22 迭代加深

阅读量：4637 次

发布时间：2019-06-09

本文共 2300 字，大约阅读时间需要 7 分钟。

poj2248 真是个新套路。还有套路剪枝...大到小和判重

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int n,D,x[110];bool bk,v[110][110];void dfs(int k){ if(bk==true)return ; if(k==D+1)return ; if(x[k-1]>n)return ; if(x[k-1]==n) { bk=true; for(int i=1;i
             
              =1;i--) { if(x[i]+x[i]
              
               =1;j--) { if(x[i]+x[j]

poj2248

送礼物折半搜索（orz cgh队长之前教我），书上叫双向搜索。又双叒叕有套路剪枝...大到小和很明显的可行性。结果dfs时居然还要先尝试选再尝试不选。。无语

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long LL;int n;int W,c[110];bool cmp(int x,int y){ return x>y;}int len;int a[10001000];inline void dfs(int k,int d){ if(k==n/2+1) { a[++len]=d; return ; } if(((LL)d)+c[k]<=W)dfs(k+1,d+c[k]); dfs(k+1,d);}int mmax;int erfen(int k){ int l=1,r=len;int ans; while(l<=r) { int mid=(l+r)/2; if(a[mid]<=k) { ans=a[mid]; l=mid+1; } else r=mid-1; } return ans;}inline void dfs2(int k,int d){ if(k==n+1) { mmax=max(mmax,d+erfen(W-d));return ; } if(((LL)d)+c[k]<=W)dfs2(k+1,d+c[k]); dfs2(k+1,d);}int main(){ scanf("%d%d",&W,&n); for(int i=1;i<=n;i++)scanf("%d",&c[i]); sort(c+1,c+n+1,cmp); len=0;dfs(1,0); sort(a+1,a+len+1);len=unique(a+1,a+len+1)-a-1; mmax=a[len]; dfs2(n/2+1,0); printf("%d\n",mmax); return 0;}#include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long LL;int n;int W,c[110];bool cmp(int x,int y){ return x>y;}int len;int a[10001000];inline void dfs(int k,int d){ if(k==n/2+1) { a[++len]=d; return ; } if(((LL)d)+c[k]<=W)dfs(k+1,d+c[k]); dfs(k+1,d);}int mmax;int erfen(int k){ int l=1,r=len;int ans; while(l<=r) { int mid=(l+r)/2; if(a[mid]<=k) { ans=a[mid]; l=mid+1; } else r=mid-1; } return ans;}inline void dfs2(int k,int d){ if(k==n+1) { mmax=max(mmax,d+erfen(W-d));return ; } if(((LL)d)+c[k]<=W)dfs2(k+1,d+c[k]); dfs2(k+1,d);}int main(){ scanf("%d%d",&W,&n); for(int i=1;i<=n;i++)scanf("%d",&c[i]); sort(c+1,c+n+1,cmp); len=0;dfs(1,0); sort(a+1,a+len+1);len=unique(a+1,a+len+1)-a-1; mmax=a[len]; dfs2(n/2+1,0); printf("%d\n",mmax); return 0;}