Codeforce 582 B. Once Again… 解析(思維、DP、LIS、矩陣冪)

今天我們來看看CF582B
題目連結

題目
給你一個長度為$n$的數列$a$，求$a$循環$T$次以後的最大遞增子序列(LIS)。$n\le100,T\le10^7$

前言

這題實在是搞了非常非常久，經驗過於不足，無論是矩陣快速冪的奇怪$dp$式或者是偏思維作法，都搞不太出來

<div class=“VVVcopyrightAAA”;>@copyright petjelinux 版權所有<br>
<a href=“https://www.cnblogs.com/petjelinux/”>觀看更多正版原始文章請至petjelinux的blog</a></div>

想法

首先，要來講一下$LIS$的作法:

1. $dp:$ 我們維護以第$i$個元素為結尾的$LIS$長度為$dp[i]$，轉移式$:dp[i]=\max\limits_{j=0,a[j]\le a[i]}^n{dp[i],dp[j]+1}$ 且要考慮$LIS$只有單一個元素時長度為1，所以$dp[i]$有個最小值$1$。
   複雜度:$O(n^2)$
2. 二分搜$:$ 我們維護一個$stack$，且每次加入一個元素考慮$LIS$。$stack$頂端放目前維護的$LIS$的最後一個元素，如果新元素$\ge$頂端的元素，那就加入。如果新元素$<$頂端的元素，那麼我們可以二分搜目前維護的$LIS$中第一個大於新元素的元素，並且替換為新元素，如此一來，因為我們換了一個比較小的元素上去，且不影響目前的$LIS$長度，因此整個$stack$在之後能獲得更好的遞增子序列的「潛力」就變高了。非常建議直接看code思考為什麼這樣做
   複雜度:$O(n\lg(n))$

int LIS(){  
  int sta[_n*_n],top=0;  
  sta[top++]=a[0];  
  rep(i,1,nn){  
    if(a[i]>=sta[top-1])sta[top++]=a[i];  
    else *upper_bound(sta,sta+top,a[i])=a[i];  
  }  
  return top;  
}  

回歸正題，這題有兩種做法，偏思維作法或者是奇怪$dp$式做法。

1. 偏思維作法
   畢竟循環($T$)太長了，而$n$又很小，所以自然地感覺應該會用到經典的$LIS$(最大遞增子序列)問題再加上一些觀察。
   注意到，最慢最慢在數列$a$循環$n$次以後，$LIS$會重複某個字元。也就是如果每次循環我們都取一個相異的元素，那麼$n$次循環以後就不可能再取到相異的元素了。而因此，我們會想要去維護長度為$n^2$的$LIS$(如果$T>n$)。
   現在，如果$T\le n$，那麼我們只要暴力算出$LIS$就行，畢竟$n$很小。
   如果$T>n$，觀察到，因為$T>n$，所以我們可以想像得出，整串$LIS$一定有非常多重複的數字，整串$LIS$會先遞增，然後到某個數字開始重複，接著在尾端繼續遞增。
   那麼我們只要先算出數列$a$中最多重複出現幾次同樣的數字，並且算出長度$n^2$的$LIS$以後，由於我們知道當$T>n$時，至少會有$T-n$次$a$數列的循環會貢獻給$LIS$同樣的數字，因此，解答就是:$LIS(長度n^2的)+(T-n)\times(出現次數最多的數字)$。(想法來源)
   還有另一個可能會想到的作法，但是複雜度會高一些，直接放連結

2. 奇怪$dp$式做法:
   其實這個做法是矩陣快速冪，但我不知道為什麼想得到這種狀態
   考慮$dp$狀態: $dp[i][j]$表示「目前為止考慮過的循環節」(考慮過幾個循環節並沒有在狀態中)的，開頭元素$\ge a[i]$且結尾為最後一個循環的第$j$個元素的$LIS$長度。
   而會有一個轉移式$:dp_{p+q}[i][j]=\max\limits_{k=0}^n{dp_p[i][k]+dp_q[k][j]}$(就是把兩個對於(不/相)同長度循環節的$LIS$接起來)
   其中$dp_p$表示目前這個$dp$狀態考慮的數列長度是$p\times n$(也就是$p$個循環節)
   我們想要求的是$dp_{nT}$，而我們可以用樸素的$dp$算法($O(n^2)$的方法)來算出$dp_1$。
   把$dp[][]$看成是矩陣，而一次轉移看成是一次矩陣乘法，那麼就可以用矩陣快速冪算出來了。
   要注意如果在算$dp[i][j]$時如果$a[i]>a[j]$代表這種可能不可能發生，要給一個極小值。

複雜度:偏思維作法中較慢的$:O(n^4)$、偏思維作法中較快的想法但是沒用二分搜$LIS:O(n^4)$、矩陣快速冪$:O(n^3\lg(T))$、偏思維作法中較快的想法且有用二分搜$:O(n^2\lg(n^2))$

程式碼(偏思維作法中較慢的):

const int _n=110;  
int tt,a[_n*_n],st[_n*_n],ed[_n*_n],num[310];  
ll n,nn,t;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>t;rep(i,0,n){cin>>a[i];num[a[i]]++;} nn=min(n*n,n*t);  
  rep(i,n,nn)a[i]=a[i%n];  
  rep(i,0,nn){ed[i]=1;{rep(j,0,i)if(a[j]<=a[i])ed[i]=max(ed[i],ed[j]+1);}}  
  per(i,0,nn){st[i]=1;{per(j,i+1,nn)if(a[j]>=a[i])st[i]=max(st[i],st[j]+1);}}  
  int maxx=-1;  
  if(t<n)rep(i,0,nn)maxx=max(maxx,ed[i]);  
  else rep(i,0,nn)maxx=max(maxx,ed[i]+st[i]-1+num[a[i]]*(t-n));  
  cout<<maxx<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission

程式碼(偏思維作法中較快的想法但是沒用二分搜):

const int _n=110;  
int tt,a[_n*_n],dp[_n*_n],num[310];  
ll n,nn,t,k;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>t;rep(i,0,n){cin>>a[i];num[a[i]]++;k=max(k,num[a[i]]);}  
  nn=min(n*n,n*t);  
  rep(i,n,nn)a[i]=a[i%n]; dp[0]=1;  
  rep(i,1,nn){  
    dp[i]=1;  
    rep(j,0,i)if(a[j]<=a[i])dp[i]=max(dp[i],dp[j]+1);  
  }  
  if(t>n){  
    int ans=k*(t-n);  
    int maxx=0;rep(i,0,nn)maxx=max(maxx,dp[i]);  
    ans+=maxx;  
    cout<<ans<<'\n';  
  }else{  
    int maxx=0;rep(i,0,nn)maxx=max(maxx,dp[i]);  
    cout<<maxx<<'\n';  
  }  
  return 0;  
}  

標頭、模板請點Submission看
Submission

程式碼(矩陣快速冪):

const int _n=110;  
int t,n,a[_n];  
struct mat{  
  int a[_n][_n];  
  mat(){memset(a,0,sizeof a);}  
  mat operator*(const mat& rhs)const{  
    mat res;  
    rep(i,0,n)rep(j,0,n){  
      res.a[i][j]=-1e5;  
      rep(k,0,n)res.a[i][j]=max(res.a[i][j],a[i][k]+rhs.a[k][j]);  
    }  
    return res;  
  }  
  mat operator^(int b){  
    mat res,tmp=*this;  
    while(b){  
      if(b&1)res=res*tmp;  
      b>>=1;tmp=tmp*tmp;  
    }  
    return res;  
  }  
};  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>t;rep(i,0,n)cin>>a[i]; mat ans;  
  rep(i,0,n)rep(j,0,n){  
    if(a[i]>a[j]){ans.a[i][j]=-1e5;continue;}  
    ans.a[i][j]=1;  
    rep(k,0,j)if(a[k]<=a[j])ans.a[i][j]=max(ans.a[i][j],ans.a[i][k]+1);  
  }ans=ans^t;  
  int maxx=0;rep(i,0,n)rep(j,0,n)maxx=max(maxx,ans.a[i][j]);  
  cout<<maxx<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission

程式碼(偏思維作法中較快的想法且有用二分搜):

const int _n=110;  
int tt,a[_n*_n],num[310];  
ll n,nn,t,k;  
int LIS(){  
  int sta[_n*_n],top=0;  
  sta[top++]=a[0];  
  rep(i,1,nn){  
    if(a[i]>=sta[top-1])sta[top++]=a[i];  
    else *upper_bound(sta,sta+top,a[i])=a[i];  
  }  
  return top;  
}  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>t;rep(i,0,n){cin>>a[i];num[a[i]]++;k=max(k,num[a[i]]);}  
  nn=min(n*n,n*t);  
  rep(i,n,nn)a[i]=a[i%n];  
  if(t>n){  
    int ans=k*(t-n);  
    ans+=LIS();  
    cout<<ans<<'\n';  
  }else cout<<LIS()<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission