洛谷P2340 奶牛会展

用下标表示智商，值表示情商

 

1 #include 
     
        2 #define For(i,j,k) for(int i=j;i<=k;i++)  3 using namespace std ;   4  5 const int N = 411 ;  6 int n,m ;  7 int a[N],b[N],f[800011] ;  8  9 inline int read() 10 {11     int x = 0 , f = 1 ; 12     char ch = getchar() ; 13     while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 14     while(ch>='0'&&ch<='9') { x = x * 10+ch-48 ; ch = getchar() ; } 15     return x * f ;  16 }17 18 int main() 19 {20     n = read() ; 21     For(i,1,n) {22         a[i]=read(),b[i]=read() ; 23         if(a[i]>0) m+=a[i] ; 24     }25     m=m<<1 ; 26     memset(f,-127/3,sizeof f) ; 27     f[m/2] = 0 ; 28     For(i,1,n) {29         if(a[i]>0) 30           for(int j=m;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]+b[i]) ; 31         if(a[i]<=0) 32           For(j,0,m+a[i]) f[j]=max(f[j],f[j-a[i]]+b[i]) ; 33     }34     35     int k = m/2 ; 36     int ans = 0 ; 37     For(i,0,k) 38       if( f[i+k]>=0&&i+f[i+k]>=ans ) 39           ans = i+f[i+k] ; 40     printf("%d\n",ans) ; 41     return 0 ; 42 }