題意即構造最長排列使得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':' '); }
沒有留言:
張貼留言