• <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>

            The Fourth Dimension Space

            枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

            9.20上海東華賽區網絡賽H題 health (Dp+Dfs+Bit Operation)

            Health

             

            Unfortunately YY gets ill, but he does not want to go to hospital. His girlfriend LMY gives him N kinds of medicine, which may be helpful. It is not a good idea to take all of them, since taking several different kinds of medicine may cause undesirable side effects. Formally speaking, for each subset S of the N kinds of medicine (excluding the empty set), it has a health value v(S). If YY chooses to take a combination T of the medicines, the final effect to his illness is the sum of health values of all non-empty subsets of T.

            YY wants to get healthy as quickly as possible, so the final effect of the medicines he takes should be as great as possible. Of course, YY may choose to take nothing, thus having a zero final effect, if he is too unlucky that all other alternatives he can get are negative…

             

            Input

             Input contains multiple test cases.

            For each test case, the first line contains a positive integer N (N16), the number of different kinds of medicine YY received from LMY.

            The second line contains a single integer M (0M2N).

            M lines follow, representing a list of health values.

            Each of the M lines contains 2 integers, s (1s<2N) and v (-10000≤v≤10000), indicating a subset of the N kinds of medicine and its health value. Write s in binary representation and add leading zeros if needed to make it exactly N binary digits. If the ith binary digit of s is 1, then the subset it represents includes the ith kind of medicine; otherwise it does not.

            It is guaranteed that no two lines of the list describe the same subset. All non-empty subsets that do not appear in the list have health value 0.

            Input ends with N=0.

             

            Output

             

            For each test case, output one line with only one integer, the maximum final effect that can be achieved.

             

            Sample Input

            2

            3

            1 10

            2 -1

            3 100

            0

             Sample Output

             109





            比賽的時候,看到這道題過的人很多,但是自己卻沒什么思路,非常郁悶,一看題就知道肯定是個DP,可是究竟怎么動態規劃呢?想了半天也想不出來,一直卡在這個題上,后來有個同學提示了我方法,這才明白過來,原來這里面還有位運算,看來我平時缺少位運算方面的訓練了。。。哎 我還是太水。。。
            分析:這個題的DP思想是把所有1 to 2^n-1的狀態所對應的健康值都算出來,然后再其中取一個最大值。我們看看他是如何狀態轉移的:
                        假設 n=3  現在考慮 1 1 1(7,從左到右分別是第3,2,1種藥品) 這種狀態,如果第三種藥品不使用,那么相當于0 1 1 產生的 總健康值;
                        這個健康值已經由它的子結構得到。
                        如果使用第三種藥品,那么我們進行一次DFS,將他對應的所有的有效狀態(無效狀態對應為0即可)對應的健康值加起來,這樣就得到了
                        使用第三種藥物的總健康值。
                        我們將上述子結構和DFS得到的結果相加,便得到了當前狀態下的總健康值。
            我們做一個循環,i from 1to 2^n-1 ,把所有情況對應的健康值算出來,然后再其中取一個最大值即可。(位運算很重要!)

            #include<iostream>
            using namespace std;
            #define MAX (1<<17)

            int value[MAX];
            int dp[MAX];
            int bin[20];
            int n,m;
            int sum;
            int ans;

            void dfs(int i,int p)
            {

                
            if(i<0)
                
            {
                    sum
            +=value[p];
                    
            return ;
                }

                
            else if(bin[i]==1)
                    dfs(i
            -1,p+(1<<i));
                dfs(i
            -1,p);
            }



            void solve(int n)
            {
                
            int now=( (1<<n)-1 );
                
            int i;
                
            int j=1;
                
            int k=-1;
                
            for(i=1;i<=now;i++)
                
            {
                    sum
            =0;
                    memset(bin,
            0,sizeof(bin));
                    j
            =1;
                    k
            =-1;
                    
            while(j*2<=i)
                    
            {

                        
            if(j&&i)
                        
            {
                            k
            ++;
                            bin[k]
            =1;
                        }

                        
            else 
                        
            {
                            k
            ++;
                            bin[k]
            =0;
                        }

                        j
            *=2;

                    }

                    dfs(k,j);
                    dp[i]
            =dp[i-j]+sum;
                    
            if(dp[i]>ans)
                    ans
            =dp[i];
                }



            }



            int main()
            {
                
            int i;
                
            while(scanf("%d",&n))
                
            {
                    ans
            =0;
                    memset(value,
            0,sizeof(value));
                    
            if(n==0)
                        
            break;
                    scanf(
            "%d",&m);
                    
            for(i=1;i<=m;i++)
                    
            {

                        
            int a,b;
                        scanf(
            "%d%d",&a,&b);
                        value[a]
            =b;
                    }

                    solve(n);
                    printf(
            "%d\n",ans);

                }

                
            return 0;
            }






            做了這個題,突然想起了將10進制轉化成2進制的方法,不斷模除2,取余數,但是一直沒有深究,今天終于明白了,原來如果把這個十進制數考慮成2進制,右移一位相當于除以2,模除2就是把最后那一位給取出來了,不斷的模除2,就把這個2進制數一位一位的取出。
            PS :感謝那位提示我思路的同學

            posted on 2009-09-21 14:28 abilitytao 閱讀(1305) 評論(4)  編輯 收藏 引用

            評論

            # re: 9.20上海東華賽區網絡賽H題 health (Dp+Dfs+Bit Operation) 2009-09-21 15:48 OwnWaterloo

            > 原來如果把這個十進制數考慮成2進制
            在C/C++中,整數本來就是按2進制而不是按10進制存儲的。
            不存在考慮成2進制的說法。

            > 突然想起了將10進制轉化成2進制的方法
            10進制是表象, 2進制才是本質。
            10進制只存在于輸入輸出的過程中, 變量最終是按2進制存儲。



            > 右移一位相當于除以2,模除2就是把最后那一位給取出來了
            > 不斷的模除2,就把這個2進制數一位一位的取出。
            int i,d;
            d = i % 2u;
            i /= 2u;

            如果你使用的編譯器不是古董,第2、3行代碼也會分別被編譯為位與、移位—— 不一定真的需要寫為 & , >>= —— 而不是除法。

              回復  更多評論   

            # re: 9.20上海東華賽區網絡賽H題 health (Dp+Dfs+Bit Operation) 2009-09-21 19:08 abilitytao

            @OwnWaterloo
            呵呵 謝謝指點 學習了^_^  回復  更多評論   

            # re: 9.20上海東華賽區網絡賽H題 health (Dp+Dfs+Bit Operation) 2009-09-21 19:47 qwe

            當時也想到了 , 因為這復雜度沒敢寫!LZ你能分析下這復雜度嗎?  回復  更多評論   

            # re: 9.20上海東華賽區網絡賽H題 health (Dp+Dfs+Bit Operation) 2009-09-30 18:09 abilitytao

            @qwe
            最低2^16 最高2^32
            折中一下 似乎可以接受 對了 請問你有更好的方法嗎?   回復  更多評論   

            国产精品久久久久久吹潮| 久久久久久久国产免费看| 少妇熟女久久综合网色欲| 国产欧美久久久精品影院| 久久er99热精品一区二区| 国产精品美女久久久久AV福利| 久久国产福利免费| 国内高清久久久久久| 丰满少妇人妻久久久久久| 亚洲欧美另类日本久久国产真实乱对白 | 欧美午夜A∨大片久久 | 久久嫩草影院免费看夜色| 无码AV中文字幕久久专区| 久久精品综合一区二区三区| 日韩AV无码久久一区二区 | 久久天天躁狠狠躁夜夜2020| 久久久久亚洲AV无码专区体验| 久久国产成人| 久久久久国产一级毛片高清版| 亚洲精品国产第一综合99久久| 狠狠色丁香久久综合婷婷| 精产国品久久一二三产区区别| 精品国产青草久久久久福利| 丰满少妇高潮惨叫久久久| 77777亚洲午夜久久多人| 久久综合视频网站| 久久久久国色AV免费观看| 国产成人久久精品麻豆一区| 国产亚洲综合久久系列| 无码国产69精品久久久久网站| 亚洲欧洲久久久精品| 欧美伊人久久大香线蕉综合69| 国产精品va久久久久久久| 精品久久久久久无码中文字幕 | 久久精品国产亚洲AV影院| 久久久久香蕉视频| 亚洲?V乱码久久精品蜜桃| 久久久久人妻一区精品果冻| 欧美日韩精品久久久久| 一级做a爰片久久毛片免费陪| 伊人久久国产免费观看视频|