2016年1月26日 星期二

[Codeforces 100488M][ACM ICPC 2014-2015]Construct a Permutation

先說答案怎麼構吧,看程式碼就知道了Orz

再來是說明為甚麼它是最大的
回顧我們找LIS(Longest Increasing Subsequence)的過程,DP[i]代表目前長度為i的LIS最後一個元素的最小值
其中,每讀進序列的一個元素,要嘛LIS最長的長度增加,不然就是某個DP[i]被更新變小(因為一個排列中沒有重複的元素)
又可以發現,當某個DP[i]被更新變小的時候,這些曾經在同一個i被存過的元素可以構成某個DS(Descreasing Subsequence)!
因此,把所有這樣產生的DS長度取最大值,叫它M吧,那麼這個序列的LDS(Longest DS)長度$\geq$M
可以發現,如果限制LIS的長度$\leq$A,LDS的長度$\leq$B,那麼i最大可以到A,而每個DP[i]又最多被更新B次,因此可以得到序列長度$\leq$A*B,也就是以下程式碼生出序列的長度!

code:
#include<cstdio>
int A,B;
int main()
{
    while(scanf("%d%d",&A,&B)==2)
    {
        printf("%d\n",A*B);
        for(int i=0;i<A;i++)for(int j=B-1;j>=0;j--)
        {
            if(i!=0||j!=B-1)putchar(' ');
            printf("%d",i*B+j+1);
        }
        puts("");
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原