1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=110;
 5 int n;
 6 int ans;
 7 int totalS,totalF;
 8 struct node
 9 {
10     int s,f;
11 }a[maxn];
12 int sum[maxn];
13 void dfs(int cnt)
14 {
15     if(cnt==n)
16     {
17         if(totalS>=0 && totalF>=0)
18             ans=max(totalS+totalF,ans);
19         return;
20     }
21     if(a[cnt].s+a[cnt].f<0 && totalS+totalF<ans) return;
22     if(totalS+totalF+sum[cnt]<=ans) return;
23 
24     totalS+=a[cnt].s;
25     totalF+=a[cnt].f;
26     dfs(cnt+1);
27 
28     totalS-=a[cnt].s;
29     totalF-=a[cnt].f;
30     dfs(cnt+1);
31 }
32 bool cmp(const node & n1,const node& n2)
33 {
34     return n1.s+n1.f>n2.s+n2.f;
35 }
36 int main()
37 {
38     scanf("%d",&n);
39     totalS=totalF=0;
40     ans=0;
41     for(int i=0;i<n;i++)
42     {
43         scanf("%d%d",&a[i].s,&a[i].f);
44         if(a[i].s>=0 && a[i].f>=0)
45         {
46             totalS+=a[i].s;
47             totalF+=a[i].f;
48             i--;
49             n--;
50         }
51         else if(a[i].s<0 && a[i].f<0)
52         {
53             i--;
54             n--;
55             continue;
56         }
57     }
58     ans=totalS+totalF;
59     sort(a,a+n,cmp);
60     memset(sum,0,sizeof(sum));
61     for(int i=n-1;i>=0;i--)
62     {
63         if(a[i].s+a[i].f<=0) sum[i]=0;
64         else sum[i]=sum[i+1]+a[i].s+a[i].f;
65     }
66     dfs(0);
67     cout<<ans<<endl;
68 }

• Re:贴个搜索的 代码 (1648) 1808636680 2014-04-03 08:06:29
• Re:贴个搜索的 代码 (1) 3435973836 2016-02-27 15:44:29