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

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>
            亚洲欧洲日本专区| 国产日产欧产精品推荐色 | 一区二区三区.www| 亚洲激情精品| 欧美高清视频在线| 亚洲深爱激情| 亚洲男女毛片无遮挡| 国产精品美女久久久久久2018| 亚洲欧美视频在线观看| 一区二区三区高清视频在线观看| 国产精品成人aaaaa网站| 亚洲一区日韩| 欧美伊人久久久久久午夜久久久久| 国产性天天综合网| 欧美成人午夜激情| 欧美精品在线观看播放| 亚洲欧美激情一区| 久久久久久免费| 一区二区三区日韩欧美精品| 亚洲自拍另类| 亚洲黄色影院| 亚洲一区二区三区乱码aⅴ蜜桃女 亚洲一区二区三区乱码aⅴ | 欧美a级在线| 欧美日本免费一区二区三区| 欧美一区二区三区播放老司机| 久久精品国产精品亚洲| av成人老司机| 欧美一区二区日韩| 夜夜嗨av色综合久久久综合网| 午夜亚洲福利| 一区二区三区欧美| 久久精品五月| 亚洲欧美日韩视频二区| 久久综合999| 欧美一区二区三区在线观看| 免费一区视频| 久久精品国产99国产精品| 亚洲黄色在线| 亚洲伊人网站| 一区二区三区久久精品| 乱码第一页成人| 久久精品免费| 国产精品v日韩精品| 欧美激情视频网站| 激情视频一区二区三区| 亚洲一区二区在线看| 99视频国产精品免费观看| 久久久99免费视频| 欧美在线高清视频| 国产精品久久久久久久9999| 亚洲欧洲日韩综合二区| 伊人精品成人久久综合软件| 亚洲免费综合| 欧美制服丝袜| 国产精品久久久91| 99精品欧美一区二区三区综合在线| 亚洲国产欧美日韩精品| 久久精品国产清高在天天线| 性伦欧美刺激片在线观看| 欧美性生交xxxxx久久久| 亚洲精品视频二区| 日韩视频免费看| 欧美国产免费| 亚洲国产精品久久人人爱蜜臀| 亚洲第一福利社区| 另类国产ts人妖高潮视频| 蜜臀a∨国产成人精品| 一区二区在线观看视频| 久久久人人人| 欧美freesex交免费视频| 在线观看一区二区精品视频| 久久婷婷成人综合色| 美女主播一区| 91久久精品www人人做人人爽| 免费一级欧美片在线播放| 亚洲激情av在线| 亚洲在线中文字幕| 国产伦精品一区二区三区高清| 欧美在线国产精品| 老司机久久99久久精品播放免费 | 日韩图片一区| 欧美日韩激情网| 亚洲天堂男人| 久久另类ts人妖一区二区| 一区在线影院| 欧美另类女人| 亚洲自拍都市欧美小说| 老司机精品久久| 99综合在线| 国产偷国产偷精品高清尤物| 久久综合九色综合久99| 亚洲三级电影全部在线观看高清| 亚洲一区二区在线观看视频| 国产亚洲人成a一在线v站| 免费观看久久久4p| 一区二区三区免费在线观看| 久久精品国产一区二区三区| 亚洲国产高潮在线观看| 欧美视频在线观看视频极品| 欧美伊人影院| 在线视频日本亚洲性| 久久理论片午夜琪琪电影网| 99国产欧美久久久精品| 欧美在线www| 亚洲高清视频一区二区| 国产精品草莓在线免费观看| 蜜桃av一区二区在线观看| 一区二区三区欧美在线观看| 美女精品在线观看| 午夜精品久久久久久99热| 亚洲高清在线播放| 国产精品一区二区三区久久| 欧美精品导航| 久久免费观看视频| 制服丝袜激情欧洲亚洲| 亚洲国产成人精品女人久久久| 欧美在线播放一区二区| 亚洲一区二区精品在线| 亚洲福利在线看| 国产亚洲欧美另类一区二区三区| 欧美精品电影| 男男成人高潮片免费网站| 亚洲一区二区三区四区中文| 亚洲国产精品成人| 免费高清在线一区| 久久国产精品久久精品国产| 亚洲免费伊人电影在线观看av| 亚洲精品视频在线观看免费| 亚洲国产欧美精品| 伊人久久综合| 韩国精品一区二区三区| 国产模特精品视频久久久久| 国产精品99一区| 欧美日韩一区在线| 欧美日韩国产高清视频| 嫩模写真一区二区三区三州| 久久这里有精品15一区二区三区| 欧美一区二区三区在线视频| 亚洲免费在线播放| 亚洲视频在线观看网站| 亚洲午夜在线| 亚洲一区欧美二区| 一本色道久久综合亚洲精品不| 最新国产成人在线观看| 亚洲国产欧美日韩另类综合| 亚洲成人在线视频播放 | 久久人人97超碰人人澡爱香蕉| 欧美在线视频a| 欧美在线网址| 久久久亚洲国产天美传媒修理工 | 亚洲男女自偷自拍图片另类| 亚洲午夜女主播在线直播| 亚洲图片激情小说| 亚洲欧美一区二区三区极速播放 | 亚洲精品久久久久久久久久久久 | 在线午夜精品| 亚洲女ⅴideoshd黑人| 午夜在线精品| 久久婷婷蜜乳一本欲蜜臀| 蜜臀a∨国产成人精品| 亚洲国产人成综合网站| 亚洲美女网站| 欧美亚洲一区三区| 久久久天天操| 欧美男人的天堂| 国产精品久久久久久模特| 国产伦精品免费视频| 欧美日本在线看| 国产精品九色蝌蚪自拍| 黄色一区二区在线| 亚洲精一区二区三区| 午夜精品福利在线| 男女av一区三区二区色多| 91久久亚洲| 亚洲欧美在线网| 蜜桃久久av一区| 欧美性色综合| 国产一区二区无遮挡| 亚洲三级影片| 久久av在线看| 亚洲高清在线观看| 亚洲在线观看视频| 美女黄网久久| 国产欧美日韩综合精品二区| 亚洲国产日韩欧美在线图片| 午夜久久久久| 亚洲日韩视频| 久久久久网址| 国产精品羞羞答答xxdd| 91久久一区二区| 久久久精品免费视频| 亚洲免费观看| 美女成人午夜| 国产一区二区三区久久悠悠色av| a4yy欧美一区二区三区| 免费久久99精品国产| 午夜影视日本亚洲欧洲精品| 欧美精品免费播放| 91久久久精品| 麻豆久久久9性大片|