• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            為生存而奔跑

               :: 首頁 :: 聯系 :: 聚合  :: 管理
              271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

            留言簿(5)

            我參與的團隊

            搜索

            •  

            積分與排名

            • 積分 - 329078
            • 排名 - 74

            最新評論

            閱讀排行榜

            評論排行榜

            先貼個搜索的代碼

             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 閱讀(400) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            亚洲精品乱码久久久久久按摩 | 97久久国产亚洲精品超碰热| 久久SE精品一区二区| 国产精品99久久99久久久| 久久精品国产欧美日韩| 亚洲精品乱码久久久久久中文字幕 | 欧美日韩精品久久免费| 成人资源影音先锋久久资源网| 国产精品久久久久影院色| 国产精品女同一区二区久久| 亚洲AV无码成人网站久久精品大| 精品乱码久久久久久久| 青青草原综合久久大伊人导航| 欧美久久综合性欧美| 久久久久人妻一区精品性色av| 久久国产劲爆AV内射—百度| 国产精品一区二区久久| 久久午夜伦鲁片免费无码| 无遮挡粉嫩小泬久久久久久久| 日韩一区二区久久久久久| 久久久久久久久久久| 日韩AV毛片精品久久久| 久久久久久久尹人综合网亚洲 | 久久人妻少妇嫩草AV蜜桃| 91精品国产高清久久久久久91| 亚洲狠狠久久综合一区77777 | 日韩AV无码久久一区二区 | 2021国产精品午夜久久| 久久国产三级无码一区二区| 久久91精品久久91综合| 久久精品国产亚洲AV无码麻豆 | 2021少妇久久久久久久久久| 一97日本道伊人久久综合影院| 亚洲综合久久久| 77777亚洲午夜久久多人| 精品乱码久久久久久久| 久久久无码精品亚洲日韩按摩| 色综合久久中文字幕无码| 久久久久久久精品成人热色戒| 亚洲国产天堂久久久久久| 久久久这里有精品|