2576-白红宇

2576

阅读量：5060 次

发布时间：2019-06-12

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

/*动态规划*/// include file#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       using namespace std;// typedeftypedef long long LL;typedef unsigned long long ULL;// #define read freopen("in.txt","r",stdin)#define write freopen("out.txt","w",stdout)#define FORi(a,b,c) for(int i=(a);i<(b);i+=c)#define FORj(a,b,c) for(int j=(a);j<(b);j+=c)#define FORk(a,b,c) for(int k=(a);k<(b);k+=c)#define FORp(a,b,c) for(int p=(a);p<(b);p+=c)#define FORii(a,b,c) for(int ii=(a);ii<(b);ii+=c)#define FORjj(a,b,c) for(int jj=(a);jj<(b);jj+=c)#define FORkk(a,b,c) for(int kk=(a);kk<(b);kk+=c)#define FF(i,a) for(int i=0;i<(a);i++)#define FFD(i,a) for(int i=(a)-1;i>=0;i--)#define Z(a) (a<<1)#define Y(a) (a>>1)const double eps = 1e-6;const double INFf = 1e10;const int INFi = 1000000000;const double Pi = acos(-1.0);template
                       
                         inline T sqr(T a){return a*a;}template
                        
                          inline T TMAX(T x,T y){ if(x>y) return x; return y;}template
                         
                           inline T TMIN(T x,T y){ if(x
                          
                            inline void SWAP(T &x,T &y){ T t = x; x = y; y = t;}template
                           
                             inline T MMAX(T x,T y,T z){ return TMAX(TMAX(x,y),z);}// code beginbool f[2][102][22501]; // i个人选j个人是否能否到达权w f[i][j][k] f[i-1][j'][k']int N;int G[110];int main(){ read; write; int sum,Max,num; while(scanf("%d",&N)!=-1) { sum = 0; FORi(1,N+1,1) { scanf("%d",G+i); sum += G[i]; } memset(f,0,sizeof(f)); Max = sum/2; num = N/2; for(int i=1;i<=N;i++) { for(int j=0;j<=num+1;j++) { for(int k=0;k<=Max;k++) { f[i%2][j][k] |= f[(i-1)%2][j][k]; if(j>=1&&k>=G[i]) f[i%2][j][k] |= f[(i-1)%2][j-1][k-G[i]]; } } f[i%2][1][G[i]] = true; } int ans = 0 ; for(int i=Max;i>=0;i--) { if(f[N%2][num][i]) { ans = i; break; } } if(N&1) for(int i=Max;i>=0;i--) { if(f[N%2][num+1][i]) { if(i>ans) { ans = i; } break; } } printf("%d %d\n",ans,sum-ans); } return 0;}