[Codeforces 100488M][2014-2015 Samara SAU ACM ICPC Quarterfinal Qualification Contest] Construct a Permutation

原題連結

題意即構造最長排列使得LIS長度為a,LDS長度為b(Longest Decreasing Subsequence)
那麼...原本以為是要直接用DP做的東西導致一直都沒有想法，所以寫個暴搜搜看看小測資的答案，結果還是沒想法Orz
最後是聽別人說可以直接構造解才寫了一個看起來很有道理的東西(?
========================
1/27補
答案最大值為a*b的證明如下：

令DP[i]代表長度為i的LIS結尾的最小值，那麼在求LIS的過程中，在結尾每加入一個新數字x，對於DP[i]的影響有兩種情況：(令DP陣列目前的大小為m，目前序列長度為n)

1. x>DP[m-1] 則 DP[m] <-- x
2. x 取代某個DP[i] where x>=DP[i-1] && x<DP[i]

第1種情況對應目前整個序列的LIS長度+1
值得注意的是第二種情況，可以發現每次的更新會使得某個DP[i]越來越小，所以DP[i]本身的值會形成一個遞減數列！這可以對應到所有LDS的情況
分析一下整個DP的過程
我們想要讓整個序列的LIS長度為a，那麼最終DP陣列的大小應該要是a
而LDS的大小就會等於max(DP[j]的更新次數+1,1<=j<=a)
最好的情況就是每個DP[j]都被更新了b-1次，那麼整個序列的大小就會是a*b

最後花點時間想出構造方法就可以出解了@@
這真是太神奇了~

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);printf("%d\n",a*b);
    for(int j=1;j<=b;j++) for(int i=1;i<=a;i++) printf("%d%c",(b-j)*a+i,i==a&&j==b?'\n':' ');
}