为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 271373
  • 排名 - 83

最新评论

阅读排行榜

评论排行榜

先贴个搜索的代码

 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 }



posted on 2010-08-10 11:35 baby-fly 阅读(288) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理