湖南多校对抗赛（2015.03.28） A Rectangle

 1 // File Name: a.cpp
 2 // Author: darkdream
 3 // Created Time: 2015年03月28日 星期六 12时13分56秒
 4 
 5 #include<vector>
 6 #include<list>
 7 #include<map>
 8 #include<set>
 9 #include<deque>
10 #include<stack>
11 #include<bitset>
12 #include<algorithm>
13 #include<functional>
14 #include<numeric>
15 #include<utility>
16 #include<sstream>
17 #include<iostream>
18 #include<iomanip>
19 #include<cstdio>
20 #include<cmath>
21 #include<cstdlib>
22 #include<cstring>
23 #include<ctime>
24 #define LL long long
25 
26 using namespace std;
27 int t;
28 int n ;
29 int sum ;
30 int dp[10005];
31 int main(){
32     scanf("%d",&t);
33     while(t--)
34     {
35         sum = 0 ; 
36         int tt = 0 ;
37         scanf("%d",&n);
38         int ta, tb; 
39         memset(dp,0,sizeof(dp));
40         dp[0] = 1;
41         int tsum = 0 ; 
42         for(int i = 1;i <= n; i ++)
43         {
44            scanf("%d %d",&ta,&tb);
45            
46           if(ta == 2 )
47               sum += tb;
48           else{
49              tsum += tb ;
50              for(int i = tsum;i >= 0 ;i -- )
51              {
52                if(dp[i] != 0 )
53                {
54                   dp[i+tb] = 1; 
55                }
56              }
57           }
58         }
59         //rintf("***%d %d\n",sum,tsum);
60         for(int i = tsum /2 ;i >= 0 ;i --)
61         {
62           if(dp[i] != 0 )
63           {
64              sum += max(i,tsum-i);
65              break;
66           }
67         }
68         printf("%d\n",sum);
69              
70     }
71 return 0;
72 }