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

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>
            99国产精品国产精品久久 | 日韩视频永久免费| 久久大逼视频| 国产日韩精品入口| 欧美一区视频在线| 亚洲欧美第一页| 国产精品中文字幕在线观看| 一个色综合导航| 99国产精品| 噜噜噜在线观看免费视频日韩| 国产一区二区精品久久91| 欧美一区二区三区电影在线观看| 99国产精品久久| 国产精品护士白丝一区av| 亚洲在线视频| 欧美一区二区日韩| 影音先锋日韩资源| 亚洲激情影视| 欧美日韩大片| 欧美在线1区| 久久久999精品| 狠狠爱www人成狠狠爱综合网| 久久综合久久久久88| 久久精品二区三区| 亚洲精品日韩一| 一本久道久久久| 国产午夜精品美女毛片视频| 久久久夜色精品亚洲| 久久精品一区蜜桃臀影院| 亚洲人成网站色ww在线| 日韩视频一区二区三区在线播放| 欧美视频专区一二在线观看| 久久国产精品久久久久久| 久久精品理论片| 一本在线高清不卡dvd| 欧美亚洲免费高清在线观看| 国产亚洲精久久久久久| 久久免费少妇高潮久久精品99| 久久影音先锋| 午夜精彩视频在线观看不卡 | 免费美女久久99| 欧美日韩另类字幕中文| 久久成人羞羞网站| 欧美夫妇交换俱乐部在线观看| 午夜精彩国产免费不卡不顿大片| 久久免费国产| 香蕉av777xxx色综合一区| 麻豆久久精品| 欧美亚洲在线| 欧美精品久久久久久久免费观看 | 亚洲国产婷婷香蕉久久久久久| 一区二区三区四区五区视频 | 欧美韩日一区二区三区| 久久综合国产精品台湾中文娱乐网| 欧美破处大片在线视频| 久热这里只精品99re8久| 欧美日韩午夜视频在线观看| 久久精品视频免费| 欧美午夜不卡影院在线观看完整版免费| 午夜在线播放视频欧美| 欧美精品亚洲精品| 欧美顶级大胆免费视频| 国产自产在线视频一区| 亚洲图片欧美午夜| 日韩视频一区二区三区在线播放免费观看 | 国产精品免费一区二区三区观看| 欧美aa国产视频| 一区精品久久| 久久在线视频| 欧美a级在线| 激情视频一区二区三区| 欧美一区亚洲一区| 久久精品国产99国产精品| 国产精品久久久久久久久免费樱桃 | 91久久在线观看| 美日韩精品免费观看视频| 久久一区欧美| 精品动漫3d一区二区三区免费| 亚洲一区二区免费视频| 亚洲一区二区欧美| 免费不卡视频| 亚洲激情第一区| 99精品黄色片免费大全| 欧美日韩高清在线| 亚洲色诱最新| 亚洲欧美一区二区三区久久| 国产亚洲欧美色| 久久米奇亚洲| 久久影院午夜片一区| 在线国产精品播放| 蜜桃久久av一区| 一区二区欧美日韩视频| 性色av一区二区三区在线观看 | 久久精品亚洲一区二区| 欧美sm视频| 亚洲午夜国产成人av电影男同| 欧美日韩亚洲网| 亚洲自拍偷拍一区| 美女精品一区| 99视频精品全部免费在线| 欧美女激情福利| 亚洲精品少妇| 久久国产精品第一页| 一区二区在线视频播放| 欧美国产综合| 亚洲欧美日韩国产一区二区三区| 欧美fxxxxxx另类| 在线视频你懂得一区| 国产精品99免视看9| 久久香蕉国产线看观看网| 最近中文字幕mv在线一区二区三区四区 | 欧美亚洲视频在线看网址| 久久综合九色欧美综合狠狠| 亚洲国产另类精品专区| 欧美高清视频一区二区| 亚洲一区欧美二区| 欧美激情一区二区在线| 亚洲欧美国产va在线影院| 国产中文一区二区三区| 欧美精品久久久久久| 午夜精品久久久久久久蜜桃app| 欧美国产第一页| 欧美一级理论性理论a| 亚洲国产日韩美| 国产嫩草影院久久久久| 欧美精品一区二区三区蜜臀| 午夜激情久久久| 日韩亚洲欧美成人| 欧美激情在线有限公司| 久久深夜福利| 亚洲欧美日韩精品| 99视频超级精品| 亚洲国产精品日韩| 国产亚洲福利| 国产精品久久久久影院色老大 | 欧美日本韩国一区二区三区| 久久九九国产精品| 欧美影院成年免费版| 国产精品99久久久久久有的能看| 欧美成人免费在线观看| 久久久国际精品| 久久精品人人做人人爽电影蜜月| 亚洲色图制服丝袜| 日韩一区二区免费高清| 国产日韩精品综合网站| 欧美精品在线观看91| 麻豆精品视频在线| 久久综合给合久久狠狠狠97色69| 久久日韩精品| 久久精品日韩| 欧美中文字幕在线观看| 一区二区三区高清不卡| 欧美激情一区二区三区在线视频观看 | 国产精品三级久久久久久电影| 欧美人与禽性xxxxx杂性| 欧美顶级艳妇交换群宴| 麻豆av一区二区三区久久| 久久在线播放| 亚洲毛片视频| 国产精品美女一区二区| 国产精品一区二区你懂得| 国产日韩欧美日韩| 亚洲第一在线视频| 99国产一区| 欧美一区二区三区免费观看视频| 久久久五月婷婷| 亚洲黄色一区| 亚洲视频一二区| 久久久久久久一区二区三区| 免费观看30秒视频久久| 欧美视频你懂的| 激情五月综合色婷婷一区二区| 亚洲日本aⅴ片在线观看香蕉| 亚洲色图制服丝袜| 久久亚洲私人国产精品va| 亚洲国产婷婷| 午夜在线精品| 欧美日韩国产免费观看| 国产亚洲精品aa午夜观看| 99riav1国产精品视频| 久久成人综合网| 亚洲精品网站在线播放gif| 小黄鸭视频精品导航| 欧美啪啪一区| 一区二区在线免费观看| 亚洲欧美日韩第一区| 亚洲国产第一| 欧美亚洲一级| 国产精品白丝黑袜喷水久久久| 精品1区2区3区4区| 香蕉视频成人在线观看 | 一区二区三区欧美在线| 蜜臀av国产精品久久久久| 亚洲视频大全| 欧美精品激情blacked18| 怡红院精品视频在线观看极品| 亚洲欧美高清| 日韩视频免费看| 欧美国产高清| 亚洲国产婷婷香蕉久久久久久99|