青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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個1,j有6種情況。
dp[i][0] = dp[i - 1][1] 表示偶數個1,且最后一個1在末尾。
dp[i][1] = dp[i - 1][0] + dis 表示奇數個1,且最后一個1在末尾。
dp[i][2] = f[i - 1][2] + f[i - 1][0] 表示偶數個1,且最后一個1不在末尾。
dp[i][3] = f[i  - 1][3] + f[i - 1][1] 表示偶數個1,且最后一個1不在末尾。
dp[i][4] = f[i - 1][4] + (dis - 1) * f[i - 1][0] 表示偶數個1,且最后一個是0不在末尾。
dp[i][5] = f[i - 1][5] + (dis - 1) * f[i - 1][0] 表示偶數個1,且最后一個是0不在末尾。
上面六個關系式列舉了所以情況,但是只用到了(dp[i][0], dp[i][1], dp[i][3], dp[i][5])四個式子。

友情提示,ans是超過int的,用long long吧,我因為這個吃了三次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 閱讀(245) 評論(0)  編輯 收藏 引用 所屬分類: 動態規劃
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美日韩国产综合视频在线观看中文 | 亚洲裸体俱乐部裸体舞表演av| 久久精品视频在线| 国产日韩在线看| 噜噜噜在线观看免费视频日韩| 久久久久久一区二区| 樱桃成人精品视频在线播放| 欧美成人第一页| 欧美人牲a欧美精品| 亚洲欧美日韩综合| 欧美一级淫片播放口| 亚洲国产日本| 亚洲精品中文字幕在线| 国产精品亚洲网站| 欧美高清hd18日本| 欧美精品在线观看| 性18欧美另类| 久久免费视频一区| 亚洲自拍偷拍视频| 久久久久久免费| 国产精品99久久久久久人 | 欧美成人精品一区二区三区| 欧美精品色一区二区三区| 欧美一区二区三区四区在线| 久久精品中文字幕免费mv| 在线视频你懂得一区| 欧美综合第一页| 99国产精品久久久久久久久久| 亚洲一区三区视频在线观看 | 国产欧美日韩在线| 亚洲欧洲精品一区二区三区| 国产精品初高中精品久久| 免费看成人av| 国产精品久久久久久av下载红粉 | 欧美专区福利在线| 欧美麻豆久久久久久中文| 久久爱91午夜羞羞| 欧美日韩一区在线| 欧美高清视频一区| 国产亚洲精品久久久| 亚洲精品久久久久中文字幕欢迎你 | 欧美激情91| 国产日韩亚洲欧美| 亚洲一二三区精品| 99www免费人成精品| 久久久夜色精品亚洲| 久久不射2019中文字幕| 欧美午夜激情在线| 亚洲精品资源| 日韩视频三区| 欧美大片免费观看在线观看网站推荐| 性欧美xxxx视频在线观看| 欧美日韩国产小视频| 亚洲高清精品中出| 一区二区三区我不卡| 亚洲一区二区高清| 亚洲欧美中文日韩在线| 欧美日韩免费观看一区三区| 亚洲黑丝在线| 91久久久亚洲精品| 牛牛影视久久网| 久久综合色婷婷| 国内精品久久久久影院色 | 在线视频日韩精品| 亚洲综合精品自拍| 国产精品免费观看在线| 亚洲少妇一区| 亚洲在线一区| 国产美女扒开尿口久久久| 亚洲无毛电影| 久久国产88| 在线日韩视频| 欧美第一黄色网| 99re6热在线精品视频播放速度| 99re66热这里只有精品4| 欧美日韩视频一区二区三区| 一区二区高清在线| 欧美一区二区三区日韩| 国内精品国语自产拍在线观看| 久久精品成人一区二区三区蜜臀| 久久天堂av综合合色| 亚洲激情一区二区三区| 欧美日韩高清在线一区| 亚洲免费中文| 免费91麻豆精品国产自产在线观看| 在线成人av.com| 欧美精品激情在线观看| 亚洲特级片在线| 久久嫩草精品久久久精品| 亚洲丁香婷深爱综合| 欧美日韩另类国产亚洲欧美一级| 亚洲一级在线观看| 免费在线亚洲| 一区二区三区色| 国产亚洲精品激情久久| 欧美国产91| 欧美亚洲视频一区二区| 亚洲电影第1页| 午夜精品电影| 亚洲黄色大片| 国产欧美一区二区三区另类精品| 久久久之久亚州精品露出| 亚洲精品一区二区三区婷婷月| 欧美一区二区成人| 亚洲美女精品久久| 国内精品久久久| 欧美福利精品| 亚洲自拍高清| 亚洲欧洲日本mm| 国产亚洲精品aa| 欧美日韩亚洲高清一区二区| 久久精品日韩| 亚洲伊人一本大道中文字幕| 亚洲国产mv| 噜噜爱69成人精品| 欧美一区二区视频网站| 一区二区三区三区在线| 亚洲国产天堂久久综合| 国产亚洲制服色| 国产精品国产| 欧美日韩国产成人在线免费| 久久久久久久久久久久久9999| 亚洲一区国产精品| 日韩视频一区二区三区在线播放| 久久亚洲精品视频| 午夜精品久久久久久久蜜桃app| 亚洲免费大片| 最新精品在线| 亚洲国产精品美女| 136国产福利精品导航网址| 国产日韩欧美不卡| 国产精品一区二区你懂得| 欧美日韩一区二| 欧美高清视频一区| 欧美凹凸一区二区三区视频| 久久婷婷久久| 久久人体大胆视频| 久久久一区二区| 久久免费99精品久久久久久| 久久精品二区亚洲w码| 欧美一区二区精美| 欧美影院一区| 久久aⅴ国产欧美74aaa| 久久精品国产91精品亚洲| 久久都是精品| 久久免费少妇高潮久久精品99| 久久九九热免费视频| 久久激情视频久久| 久久亚洲一区二区三区四区| 麻豆精品一区二区综合av| 噜噜噜91成人网| 欧美高清hd18日本| 欧美日韩亚洲另类| 国产精品乱码妇女bbbb| 国产女优一区| 韩国欧美一区| 亚洲欧洲日夜超级视频| 99国产精品视频免费观看| 亚洲一二三区精品| 欧美有码在线观看视频| 久久综合久久综合久久综合| 免费看成人av| 日韩亚洲在线| 欧美一区二区三区在线观看| 久久久蜜桃一区二区人| 欧美激情bt| 国产精品一级久久久| 尤物九九久久国产精品的特点| 悠悠资源网久久精品| 一区二区三区高清不卡| 欧美一区影院| 亚洲国产成人av好男人在线观看| 一本久道久久综合婷婷鲸鱼| 小辣椒精品导航| 免费看亚洲片| 国产精品美女久久久久久免费| 激情欧美一区| 亚洲一区区二区| 免费不卡欧美自拍视频| 一区二区激情视频| 久久看片网站| 国产精品成人在线| 亚洲区国产区| 欧美一区二区三区日韩视频| 亚洲国产三级在线| 欧美一区二区免费| 欧美日韩亚洲免费| 午夜精品三级视频福利| 欧美精品手机在线| 极品尤物av久久免费看| 亚洲女人小视频在线观看| 免费观看30秒视频久久| 亚洲一区日本| 欧美精品电影| 在线观看91精品国产入口| 欧美一级视频免费在线观看| 亚洲日本免费电影| 美女网站久久| 精品av久久707| 久久精品99|