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

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>
            久久久久久久久伊人| 午夜精品久久久| 欧美国产日韩一区二区| 久久天天狠狠| 日韩视频一区二区在线观看 | 久久久av水蜜桃| 亚洲国产老妈| 夜夜爽www精品| 国产免费亚洲高清| 欧美 日韩 国产 一区| 欧美日韩不卡| 欧美在线网站| 猫咪成人在线观看| 亚洲在线一区| 两个人的视频www国产精品| 一区二区三区四区国产精品| 亚洲免费一级电影| 亚洲国内自拍| 亚洲在线视频免费观看| 亚洲黄网站黄| 亚洲免费视频中文字幕| 亚洲精品一区二区网址| 午夜日韩在线观看| 99精品国产在热久久下载| 欧美一二三区精品| 正在播放亚洲| 美女视频一区免费观看| 亚洲欧美一区二区在线观看| 免费日本视频一区| 久久久精品国产一区二区三区| 欧美老女人xx| 蜜桃精品一区二区三区| 国产精品久久久久一区二区| 欧美激情a∨在线视频播放| 国产区欧美区日韩区| 亚洲理论在线| 91久久中文| 久久免费一区| 欧美中文字幕精品| 欧美亚日韩国产aⅴ精品中极品| 欧美国产精品v| 韩国av一区二区三区四区| 亚洲天堂第二页| 在线综合亚洲| 欧美日产国产成人免费图片| 欧美va天堂在线| 狠狠色狠狠色综合| 香蕉成人伊视频在线观看| 亚洲欧美国产高清va在线播| 欧美精品在欧美一区二区少妇| 欧美xxx在线观看| 红桃视频国产精品| 久久成人精品一区二区三区| 欧美一区二区三区四区高清| 国产精品国色综合久久| 99天天综合性| 亚洲一区二区三区免费观看| 欧美日韩网站| 中日韩美女免费视频网址在线观看| 亚洲精品永久免费精品| 欧美激情在线| 日韩一级精品视频在线观看| 一区二区日韩精品| 欧美涩涩网站| 亚洲在线观看免费| 久久精品一本| 亚洲高清一区二区三区| 牛牛国产精品| 日韩午夜激情av| 亚洲欧美成人| 国产午夜精品久久| 老司机久久99久久精品播放免费| 亚洲高清资源| 一本久道久久综合中文字幕 | 久久aⅴ国产紧身牛仔裤| 久久久久久伊人| 亚洲国产精品一区二区www在线| 免费日韩av| 国产精品99久久久久久久女警 | 欧美jjzz| 一本色道久久综合狠狠躁篇的优点| 亚洲一区二区三区成人在线视频精品| 欧美视频在线观看| 欧美在线视频免费观看| 欧美激情女人20p| 亚洲一二三区精品| 国产一区二区剧情av在线| 女生裸体视频一区二区三区| 日韩视频中文| 乱码第一页成人| 国产精品99久久久久久宅男| 国产一区二区0| 欧美国产91| 性视频1819p久久| 亚洲国产影院| 久久国产一区二区| 99视频精品在线| 狠狠色丁香久久婷婷综合丁香| 欧美成人亚洲成人| 亚洲欧美日韩爽爽影院| 亚洲高清资源| 久久久久久久综合| 亚洲少妇在线| 亚洲国产清纯| 国产色爱av资源综合区| 欧美日韩国产高清| 久久综合色8888| 亚洲欧美一区二区原创| 亚洲精品一区二区三区不| 蜜臀91精品一区二区三区| 亚洲欧美大片| 一区二区三区国产在线观看| 激情国产一区二区| 国产酒店精品激情| 欧美日韩成人综合天天影院| 久久蜜臀精品av| 午夜精品福利电影| 亚洲视频狠狠| 亚洲精品久久久久久久久久久| 久久先锋资源| 久久精品午夜| 欧美影院午夜播放| 亚洲欧美日韩国产中文在线| 一区二区欧美日韩视频| 亚洲日本va午夜在线电影| 影音先锋日韩有码| 国产一级一区二区| 国产性做久久久久久| 国产精品一区二区在线观看网站| 欧美日韩视频在线第一区| 欧美精品一区二区三区蜜桃| 免费看亚洲片| 欧美激情91| 欧美极品在线视频| 欧美伦理在线观看| 欧美日韩人人澡狠狠躁视频| 欧美激情亚洲综合一区| 欧美精品国产一区二区| 欧美寡妇偷汉性猛交| 欧美精品国产一区| 欧美日韩综合不卡| 国产精品激情| 国产精品亚洲成人| 国产一区在线免费观看| 国内视频一区| 91久久国产综合久久91精品网站 | 欧美手机在线| 国产麻豆综合| 含羞草久久爱69一区| 在线精品福利| 亚洲免费久久| 亚洲免费在线电影| 久久不射网站| 久久亚洲私人国产精品va| 欧美www视频| 日韩视频免费看| 亚洲欧美日韩国产综合精品二区| 欧美伊人精品成人久久综合97 | 99亚洲伊人久久精品影院红桃| 亚洲视频视频在线| 久久成人在线| 欧美激情免费观看| 国产精品日日做人人爱| 国产在线国偷精品产拍免费yy| 亚洲成色999久久网站| 99xxxx成人网| 欧美在线视频网站| 亚洲国产经典视频| 亚洲一级二级在线| 久久青草久久| 国产精品久久9| 在线看片第一页欧美| 亚洲视屏在线播放| 麻豆成人在线播放| 99精品久久久| 久久综合伊人77777尤物| 国产精品第一区| 亚洲国产99精品国自产| 午夜欧美精品| 亚洲国产日日夜夜| 欧美一区二区三区视频| 欧美久久久久| 一区在线播放视频| 亚洲在线观看免费视频| 欧美激情一二三区| 新狼窝色av性久久久久久| 欧美国产日本| 激情欧美国产欧美| 欧美中文字幕在线播放| 亚洲精品欧美极品| 蜜桃av噜噜一区二区三区| 国产欧美日韩另类一区| 一区二区三区精品在线| 欧美成人一区二区三区片免费| 亚洲一区二区三区在线视频| 欧美精品免费在线观看| 亚洲电影激情视频网站| 久久久精品视频成人| 亚洲欧美激情一区二区| 国产精品国产三级国产aⅴ9色|