先貼個搜索的代碼
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 }
下面是用dp做的
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const int maxn=100005;
5 int dp[2*maxn];
6 int main()
7 {
8 int n;
9 int s,f;
10 int down,up;
11 down=up=maxn;
12 for(int i=0;i<2*maxn;i++)
13 dp[i]=-maxn;
14 dp[maxn]=0;
15 scanf("%d",&n);
16 for(int i=0;i<n;i++)
17 {
18 scanf("%d%d",&s,&f);
19 if(s<0 && f<0)
20 {
21 continue;
22 }
23
24 if(s>0)
25 {
26 for(int j=up;j>=down;j--)
27 {
28 if(dp[j]!=-maxn)
29 {
30 dp[j+s]=max(dp[j+s],dp[j]+f);
31 }
32 }
33 up+=s;
34 }
35 else
36 {
37 for(int j=down;j<=up;j++)
38 {
39 if(dp[j]!=-maxn)
40 {
41 dp[j+s]=max(dp[j+s],dp[j]+f);
42 }
43 }
44 down+=s;
45 }
46 }
47
48 int ans=0;
49 for(int i=maxn;i<=up;i++)
50 {
51 if(dp[i]>=0 && dp[i]+i>ans)
52 ans=dp[i]+i;
53 }
54 cout<<ans-maxn<<endl;
55 }