• <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>
            posts - 7,comments - 3,trackbacks - 0

            Max Xor Sub-sequence II 
            Time Limit:1000MS  Memory Limit:32768K

            Description:

            Give you a sequence of integer numbers which are 1 or 0. You are to find the number of consecutive sub-sequence, which the xor value between all these numbers has the maximum value. The first number of the sequence is 1 and the last is 1. There are (n+1) 1’s in the sequence. N numbers will be given. The i-th number is the index of (i+1)-th 1 minus the index of i-th 1. For example: if the sequence is 1010100010001, 4 2 2 4 4 will be given.

             

            Input:

            There are multiple cases. For each case: Line 1: A single integer N (1<=N<=20000). Followed N integers ranging from 1 to 20000.

            Output:

            For each case output the result in a single line.

            Sample Input:

            4
            2 2 4 4
            5
            3 1 2 4 5
            

            Sample Output:

            49
            70
            

            Hint:

            1.1 ^ 1 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 0 ^ 0 = 0. 2.In the example, sub-sequence 10 has the maximum value ‘cause 1 xor 0 = 1;the same as 10101, 1010100010001, and so on.

            算不上DP的DP......就是處理01串的奇偶性.....
            DP[i][j]表示第i個(gè)1,j有6種情況。
            dp[i][0] = dp[i - 1][1] 表示偶數(shù)個(gè)1,且最后一個(gè)1在末尾。
            dp[i][1] = dp[i - 1][0] + dis 表示奇數(shù)個(gè)1,且最后一個(gè)1在末尾。
            dp[i][2] = f[i - 1][2] + f[i - 1][0] 表示偶數(shù)個(gè)1,且最后一個(gè)1不在末尾。
            dp[i][3] = f[i  - 1][3] + f[i - 1][1] 表示偶數(shù)個(gè)1,且最后一個(gè)1不在末尾。
            dp[i][4] = f[i - 1][4] + (dis - 1) * f[i - 1][0] 表示偶數(shù)個(gè)1,且最后一個(gè)是0不在末尾。
            dp[i][5] = f[i - 1][5] + (dis - 1) * f[i - 1][0] 表示偶數(shù)個(gè)1,且最后一個(gè)是0不在末尾。
            上面六個(gè)關(guān)系式列舉了所以情況,但是只用到了(dp[i][0], dp[i][1], dp[i][3], dp[i][5])四個(gè)式子。

            友情提示,ans是超過int的,用long long吧,我因?yàn)檫@個(gè)吃了三次WA.....

            代碼:

            #include <cstdio>
            #include <cstring>
            #include <iostream>
            using namespace std;

            int main()
            {
                long long dp[20010][7];
                long long n;
                long long dis;
                while (cin >> n)
                {
                    memset(dp, 0, sizeof(dp));
                    dp[1][0] = 0;
                    dp[1][1] = 1;
                    for (long long i = 2; i <= n + 1; ++i)
                    {
                        cin >> dis;
                        dp[i][0] = dp[i - 1][1];
                        dp[i][1] = dp[i - 1][0] + dis;
                        dp[i][3] = dp[i - 1][3] + dp[i - 1][1];
                        dp[i][5] = dp[i - 1][5] + (dis - 1) * dp[i - 1][1];
                    }
                    cout << dp[n + 1][1] + dp[n + 1][3] + dp[n + 1][5] << endl;
                }
                return 0;
            }

            posted on 2011-10-15 22:15 LLawliet 閱讀(238) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 動(dòng)態(tài)規(guī)劃
            国产精品久久波多野结衣| 91精品国产91久久久久福利| 欧美午夜精品久久久久免费视 | 伊人久久大香线蕉av不卡| 亚洲精品tv久久久久久久久 | 欧美日韩精品久久久久| 亚洲精品tv久久久久久久久久| 四虎亚洲国产成人久久精品| 亚洲中文字幕久久精品无码APP | 国产亚洲欧美精品久久久| 欧美精品福利视频一区二区三区久久久精品 | 久久精品人人做人人妻人人玩| 国产2021久久精品| 日韩精品久久久肉伦网站| 久久这里只有精品首页| 久久青青草原精品国产| 丰满少妇人妻久久久久久4| 97久久婷婷五月综合色d啪蜜芽| 久久99热精品| 青青青青久久精品国产| 亚洲伊人久久综合中文成人网| 国内精品人妻无码久久久影院 | 久久精品国产亚洲AV忘忧草18| 香蕉久久影院| 欧美一区二区精品久久| 久久亚洲精品国产亚洲老地址| 国产精品丝袜久久久久久不卡| 久久精品国产99久久久古代| 国产高潮久久免费观看| 久久ZYZ资源站无码中文动漫| 国产精品一区二区久久精品涩爱| 久久久综合九色合综国产| 久久人人爽人人爽人人片av高请| 久久久亚洲精品蜜桃臀| 久久久中文字幕日本| 国产精品欧美久久久久天天影视| 久久精品国产久精国产| 精品久久久久久综合日本| 久久精品国产99久久无毒不卡| 久久天天躁夜夜躁狠狠躁2022| 久久男人中文字幕资源站|