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

oyjpArt ACM/ICPC算法程序設計空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

A decorative fence
Time Limit:1000MS  Memory Limit:10000K
Total Submit:1548 Accepted:440

Description
Richard just finished building his new house. Now the only thing the house misses is a cute little wooden fence. He had no idea how to make a wooden fence, so he decided to order one. Somehow he got his hands on the ACME Fence Catalogue 2002, the ultimate resource on cute little wooden fences. After reading its preface he already knew, what makes a little wooden fence cute.
A wooden fence consists of N wooden planks, placed vertically in a row next to each other. A fence looks cute if and only if the following conditions are met:
?The planks have different lengths, namely 1, 2, . . . , N plank length units.
?Each plank with two neighbors is either larger than each of its neighbors or smaller than each of them. (Note that this makes the top of the fence alternately rise and fall.)
It follows, that we may uniquely describe each cute fence with N planks as a permutation a1, . . . , aN of the numbers 1, . . . ,N such that (any i; 1 < i < N) (ai − ai−1)*(ai − ai+1) > 0 and vice versa, each such permutation describes a cute fence.
It is obvious, that there are many di erent cute wooden fences made of N planks. To bring some order into their catalogue, the sales manager of ACME decided to order them in the following way: Fence A (represented by the permutation a1, . . . , aN) is in the catalogue before fence B (represented by b1, . . . , bN) if and only if there exists such i, that (any j < i) aj = bj and (ai < bi). (Also to decide, which of the two fences is earlier in the catalogue, take their corresponding permutations, find the first place on which they differ and compare the values on this place.) All the cute fences with N planks are numbered (starting from 1) in the order they appear in the catalogue. This number is called their catalogue number.


After carefully examining all the cute little wooden fences, Richard decided to order some of them. For each of them he noted the number of its planks and its catalogue number. Later, as he met his friends, he wanted to show them the fences he ordered, but he lost the catalogue somewhere. The only thing he has got are his notes. Please help him find out, how will his fences look like.

 

Input
The first line of the input file contains the number K (1 <= K <= 100) of input data sets. K lines follow, each of them describes one input data set.
Each of the following K lines contains two integers N and C (1 <= N <= 20), separated by a space. N is the number of planks in the fence, C is the catalogue number of the fence.
You may assume, that the total number of cute little wooden fences with 20 planks fits into a 64-bit signed integer variable (long long in C/C++, int64 in FreePascal). You may also assume that the input is correct, in particular that C is at least 1 and it doesn抰 exceed the number of cute fences with N planks.

Output
For each input data set output one line, describing the C-th fence with N planks in the catalogue. More precisely, if the fence is described by the permutation a1, . . . , aN, then the corresponding line of the output file should contain the numbers ai (in the correct order), separated by single spaces.

Sample Input

2
2 1
3 3

 

Sample Output

1 2
2 3 1

 

Source
CEOI 2002


也算是DP+分段統計中的經典題了 呵呵
DP的狀態表示如下
dp[style][n][i][j] :
style 代表走向 0 代表向上(也就是下次要向下) 1代表向下
n代表總共的fence數
i代表比當前選擇的fence高的fence數(注意 當前fence是一個隱藏的參數 因為該狀態不需要知道當前fence是哪個 只需要知道有多少比這個fence高 多少比這個fence低 就可以代表整個狀態)
j代表比當前選擇的fence低的fence數

這樣很直觀的得到了一個DP方程

    dp[0][i][j][k] += dp[1][i-1][j-m][k+m-1]; (m = 1 ... j (inclusive))

    dp[1][i][j][k] += dp[0][i-1][j+m-1][k-m];   (m = 1... k(inclusive))

具體請參考源代碼

 1#include <stdio.h>
 2#include <string.h>
 3
 4const int N = 21;
 5__int64 dp[2][N][N][N];
 6int n;
 7__int64 idx;
 8bool chk[N];
 9
10void pre() {
11    int i, j, m;
12
13    memset(dp, 0, sizeof(dp));
14
15    dp[0][1][0][0= 1;
16    dp[1][1][0][0= 1;
17
18    for(i = 2; i <= 20++i) {
19        for(j = 0; j < i; ++j) {
20            int k = i - j - 1;
21            for(m = 1; m <= j; ++m) 
22                dp[0][i][j][k] += dp[1][i-1][j-m][k+m-1];
23            for(m = 1; m <= k; ++m)
24                dp[1][i][j][k] += dp[0][i-1][j+m-1][k-m];
25        }
26    }
27}
28
29void DFS(int nowint last, int style, __int64 idx) {
30    if(now <= 0) return;
31    int i, j;
32    for(i = 0; i < n; ++i) if(!chk[i]) {
33        if(style == 0 && i < last) continue;
34        if(style == 1 && i > last) return;
35
36        chk[i] = true;
37        int big = 0, small = 0;
38        for(j = 0; j < n; ++j) if(!chk[j]) {
39            if(j < i) small++;
40            if(j > i) big++;
41        }
42
43        if(style == 0 || style == -1) {
44            if(idx > dp[1][now][big][small]) idx -= dp[1][now][big][small];
45            else {
46                printf("%d ", i+1);
47                DFS(now-1, i, 1, idx);    return;
48            }
49        }
50
51        if(style == 1 || style == -1) {
52            if(idx > dp[0][now][big][small]) idx -= dp[0][now][big][small];
53            else {
54                printf("%d ", i+1);
55                DFS(now-1, i, 0, idx);    return;
56            }
57        }
58        chk[i] = false;
59    }
60}
61
62int main() {
63    int ntc;
64    pre();
65    scanf("%d "&ntc);
66    while(ntc--) {
67        scanf("%d %I64d"&n, &idx);
68        memset(chk, false, sizeof(chk));
69        DFS(n, -1-1, idx);
70        putchar('\n');
71    }
72    return 0;
73}

Feedback

# re: PKU1037 A decorative fence DP+分段統計  回復  更多評論   

2007-08-18 15:57 by deoxyz
你的最后一維根本不需要啊.......這樣空間復雜度會下降不少啊...

# re: PKU1037 A decorative fence DP+分段統計  回復  更多評論   

2007-08-18 16:27 by oyjpart
真的么?
那你怎么寫的呢?

# re: PKU1037 A decorative fence DP+分段統計  回復  更多評論   

2007-08-19 10:08 by deoxyz
就你的這個程序的話 直接把所有有關最后一維的東西全部刪掉就行了,第三維完全可以用前兩維表示~而且輸出可以不用遞歸會快點~ 我ACM也剛學1年多點 有空交流交流 我QQ120148455

# re: PKU1037 A decorative fence DP+分段統計  回復  更多評論   

2007-08-19 11:05 by oyjpart
恩 是的

# re: PKU1037 A decorative fence DP+分段統計  回復  更多評論   

2007-10-10 13:28 by floyd635
的確只要三維就可以完成...
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美视频导航| 亚洲视频精选| 久久精品中文| 国内精品一区二区| 麻豆成人精品| 欧美成人综合在线| 在线视频日本亚洲性| 亚洲图中文字幕| 国产精品欧美在线| 欧美在线网址| 免费国产一区二区| 一本色道久久综合亚洲精品小说 | 99v久久综合狠狠综合久久| 亚洲国产片色| 欧美日韩亚洲成人| 久久精品最新地址| 欧美黄色一区| 性做久久久久久| 老鸭窝毛片一区二区三区| 9久草视频在线视频精品| 亚洲欧美国产精品va在线观看| 国产午夜精品久久久| 欧美xx69| 国产精品久久一区二区三区| 麻豆国产va免费精品高清在线| 欧美mv日韩mv国产网站| 一区二区欧美在线观看| 欧美影院成年免费版| 日韩一区二区精品视频| 西西裸体人体做爰大胆久久久| 怡红院精品视频| 一本色道久久综合亚洲精品不卡| 国产一区二区三区在线观看免费视频 | 欧美日韩视频第一区| 久久久久国产精品一区三寸| 欧美另类一区| 麻豆久久婷婷| 国产欧美欧美| 亚洲精品久久久久久下一站| 国产亚洲欧美另类中文 | 久久精品水蜜桃av综合天堂| 欧美片在线观看| 美女黄色成人网| 国产精品欧美日韩| 亚洲精品欧美极品| 亚洲激情在线激情| 欧美影院视频| 性色一区二区| 欧美日韩伊人| 亚洲免费观看在线观看| 91久久精品日日躁夜夜躁欧美| 亚洲综合欧美日韩| 亚洲香蕉伊综合在人在线视看| 免播放器亚洲一区| 麻豆精品一区二区综合av| 国产深夜精品| 亚洲欧美日韩精品久久亚洲区| 中国av一区| 欧美日韩精品一本二本三本| 亚洲第一区色| 亚洲激情校园春色| 久久综合给合久久狠狠色 | 亚洲视频综合| 欧美日韩视频在线观看一区二区三区| 欧美国产日韩精品| 亚洲二区在线观看| 美女在线一区二区| 欧美成人嫩草网站| 亚洲精品午夜| 欧美美女日韩| 一区二区高清视频| 亚洲欧美日韩国产另类专区| 国产精品久久久久久久电影 | 亚洲欧美国产视频| 久久久久久高潮国产精品视| 韩日欧美一区二区| 久久综合伊人77777麻豆| 欧美成人午夜激情视频| 亚洲乱码日产精品bd| 欧美激情久久久久| 亚洲免费高清视频| 午夜精品成人在线| 韩国一区二区在线观看| 欧美成年人网| 一区二区电影免费观看| 久久精品亚洲精品| 亚洲国产女人aaa毛片在线| 欧美日韩 国产精品| 亚洲永久精品大片| 美日韩精品免费| 在线午夜精品自拍| 国产日韩欧美不卡在线| 免费观看在线综合色| 一本久道久久综合婷婷鲸鱼| 久久xxxx| 亚洲美女电影在线| 国产伦精品一区二区三区免费迷| 久久久久久穴| 一区二区三区高清不卡| 久久久国产精品亚洲一区| 亚洲人成在线观看一区二区 | 久久色中文字幕| 中文av一区特黄| 免费观看成人鲁鲁鲁鲁鲁视频| 日韩一区二区精品视频| 国产揄拍国内精品对白| 欧美巨乳波霸| 久久久久久精| 亚洲系列中文字幕| 亚洲第一精品夜夜躁人人躁| 欧美一区二区三区视频在线观看| 亚洲国产高清在线观看视频| 国产精品久久久久9999吃药| 免费试看一区| 久久成人国产| 一区二区三区.www| 亚洲人精品午夜| 老牛嫩草一区二区三区日本| 亚洲欧美99| 一本色道久久综合亚洲精品高清| 很黄很黄激情成人| 国产欧美日韩麻豆91| 欧美日本高清| 欧美国产综合| 久久综合中文| 久久aⅴ国产欧美74aaa| 亚洲视频一二三| 日韩亚洲国产精品| 亚洲国产一区二区三区青草影视| 久久在线免费视频| 久久久久久香蕉网| 欧美伊人精品成人久久综合97| 亚洲视频在线视频| 一区二区三区精品视频| 日韩亚洲国产精品| 亚洲精品乱码久久久久久久久| 一区在线观看| 激情欧美一区二区| 好看的日韩av电影| 国产综合色产| 精品成人国产| 亚洲第一成人在线| 亚洲国产精品999| 亚洲国产欧美一区二区三区丁香婷| 狠狠入ady亚洲精品经典电影| 国产日韩精品视频一区| 国产日韩欧美黄色| 国语对白精品一区二区| 黑人一区二区三区四区五区| 精品88久久久久88久久久| 精品1区2区| 亚洲国产综合视频在线观看| 亚洲黄色免费网站| 日韩一级在线观看| 亚洲综合精品| 久久精品日韩欧美| 你懂的亚洲视频| 最新日韩精品| 亚洲香蕉成视频在线观看 | 一区二区三区成人精品| 香蕉乱码成人久久天堂爱免费| 午夜日韩av| 久久久噜噜噜久噜久久| 欧美jjzz| 国产精品久久久久久久久久直播 | 欧美区一区二| 国产日韩精品视频一区| 在线精品亚洲| 一区二区三区.www| 午夜精品国产| 久久中文欧美| 亚洲精品在线观看免费| 亚洲欧美www| 麻豆成人在线观看| 国产精品久久久久毛片软件| 黑人巨大精品欧美一区二区小视频| 亚洲精品视频二区| 欧美亚洲专区| 亚洲国产精品久久久久婷婷老年 | 亚洲精品在线电影| 久久www免费人成看片高清 | 亚洲一区日韩在线| 欧美国内亚洲| 激情小说亚洲一区| 亚洲免费网址| 亚洲第一在线| 午夜亚洲视频| 欧美日韩精品免费观看| 在线欧美不卡| 久久精品99久久香蕉国产色戒| 亚洲激情第一页| 久久激情综合网| 欧美视频福利| 亚洲国产高清在线| 欧美亚洲一区二区三区| 欧美电影免费观看| 久久精品国产免费看久久精品| 欧美激情一区二区| 免费日韩av| 黄色成人av网|