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

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>
            久久精品国内一区二区三区| 先锋影音久久久| 欧美大片免费久久精品三p| 一区二区三区无毛| 麻豆久久久9性大片| 嫩草伊人久久精品少妇av杨幂| 亚洲国产成人一区| 亚洲日本无吗高清不卡| 欧美日韩三级在线| 欧美一二三区精品| 久久综合亚洲社区| 中文av一区特黄| 小黄鸭视频精品导航| 亚洲电影有码| 夜夜爽夜夜爽精品视频| 国产一区二区黄| 亚洲经典三级| 国产日韩欧美精品一区| 欧美国产三区| 国产欧美亚洲一区| 亚洲第一精品电影| 国产精品美女久久久久久久| 久久噜噜噜精品国产亚洲综合 | 欧美在线一二三| 久久久久久久综合日本| 在线视频免费在线观看一区二区| 午夜欧美理论片| 一区二区激情视频| 久久精品国产久精国产一老狼| 日韩亚洲一区二区| 欧美一区二区视频网站| 一区二区高清在线| 久久久久久久999| 亚洲免费伊人电影在线观看av| 久久天天综合| 欧美亚洲免费电影| 欧美日韩国产精品一区| 久久综合伊人| 国产欧美精品日韩精品| 亚洲麻豆国产自偷在线| 在线观看欧美日本| 亚洲欧美日韩视频一区| 一本色道**综合亚洲精品蜜桃冫| 久久久久国产精品www| 亚洲综合三区| 欧美日韩精品一区二区三区| 欧美不卡视频一区发布| 国产一二三精品| 亚洲免费网站| 午夜精品理论片| 欧美午夜视频一区二区| 91久久精品一区二区别| 亚洲国产欧美一区二区三区久久 | 欧美+日本+国产+在线a∨观看| 欧美怡红院视频| 国产精品久久久一区麻豆最新章节| 亚洲国产精品v| 亚洲电影在线免费观看| 久久蜜桃精品| 免费视频亚洲| 亚洲第一区色| 久久综合亚州| 亚洲国产成人在线视频| 亚洲精品免费电影| 欧美激情在线| 亚洲毛片在线| 亚洲一区国产精品| 国产精品久久久久久亚洲调教| 99热在线精品观看| 亚洲欧美日韩国产另类专区| 国产精品久久久久久久电影| 亚洲一区免费看| 久久成人免费电影| 精品999网站| 久久这里有精品15一区二区三区| 女人色偷偷aa久久天堂| 亚洲欧洲精品成人久久奇米网| 美女网站久久| 99re66热这里只有精品4| 亚洲砖区区免费| 国产精品有限公司| 久久久久.com| 亚洲韩国日本中文字幕| 亚洲在线网站| 狠狠干狠狠久久| 欧美成人亚洲成人日韩成人| 日韩西西人体444www| 久久成人在线| 亚洲黄色一区二区三区| 欧美日精品一区视频| 亚洲欧美一区二区在线观看| 美女网站在线免费欧美精品| 亚洲美女av黄| 国产一区二区在线观看免费| 免费观看成人www动漫视频| 一区二区欧美亚洲| 能在线观看的日韩av| 亚洲网在线观看| 在线电影一区| 国产精品av久久久久久麻豆网 | 欧美激情1区2区| 午夜精品久久久久久久久久久久| 国外成人免费视频| 欧美亚洲不卡| 欧美 亚欧 日韩视频在线| 亚洲性色视频| 91久久国产综合久久| 久久久久国产精品一区| 在线视频欧美精品| 在线观看亚洲a| 国产精品捆绑调教| 欧美高清视频在线播放| 欧美在线网址| 在线亚洲电影| 亚洲日本va在线观看| 久久只有精品| 欧美一区二区三区日韩视频| 亚洲乱码国产乱码精品精98午夜| 国产一区二区三区自拍| 欧美日韩亚洲国产精品| 免费久久久一本精品久久区| 午夜日韩福利| 亚洲一区二区视频| 一本久久综合亚洲鲁鲁| 最新亚洲激情| 亚洲国产一区二区三区青草影视| 久久中文欧美| 久久国产福利国产秒拍| 午夜精品成人在线视频| 一区二区三区日韩精品视频| 最新日韩精品| 亚洲国产毛片完整版| 黑人巨大精品欧美一区二区| 国产女主播一区二区三区| 国产精品久久久久7777婷婷| 欧美精品在线一区| 欧美激情一区二区三区高清视频| 久热精品视频在线观看一区| 久久午夜电影| 麻豆成人综合网| 美国成人毛片| 欧美精品激情在线| 欧美精品一区二区三区蜜臀| 欧美激情va永久在线播放| 麻豆免费精品视频| 欧美大片免费观看| 欧美—级高清免费播放| 欧美日本三区| 国产精品海角社区在线观看| 国产精品户外野外| 国产精品人成在线观看免费| 国产精品永久免费在线| 国产欧美日韩中文字幕在线| 国产亚洲精品一区二区| 激情五月婷婷综合| 亚洲人在线视频| 一个色综合av| 久久成年人视频| 你懂的亚洲视频| 亚洲国产你懂的| 一区二区三区精品久久久| 亚洲欧美日韩视频二区| 久久久久久噜噜噜久久久精品| 六月天综合网| 欧美视频在线不卡| 国外视频精品毛片| 亚洲另类自拍| 久久国产欧美精品| 91久久国产综合久久91精品网站| 一本色道久久综合狠狠躁篇怎么玩 | 在线视频欧美日韩| 欧美在线国产精品| 欧美二区在线| 国产欧美一区二区三区在线老狼 | 亚洲欧美日本伦理| 老鸭窝毛片一区二区三区 | 美女成人午夜| 欧美日韩欧美一区二区| 国产主播一区二区三区| 亚洲激情视频网站| 久久aⅴ国产紧身牛仔裤| 亚洲国产成人精品久久| 亚洲无限乱码一二三四麻| 久久视频在线免费观看| 国产精品黄页免费高清在线观看| 国内精品久久久久伊人av| 一级日韩一区在线观看| 久久婷婷麻豆| 亚洲视频第一页| 欧美丰满高潮xxxx喷水动漫| 国产视频一区三区| 在线亚洲一区二区| 欧美黄色免费| 欧美在线观看一区二区三区| 欧美日韩亚洲91| 亚洲伦理在线免费看| 久久九九久精品国产免费直播| 亚洲美女黄色| 欧美精品久久久久久| 亚洲国产精品一区二区尤物区|