Codeforce 682 D. Alyona and Strings 解析(思維、DP)

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

題目
略，請直接看原題。

前言

a

想法

首先會感覺應該是類似$LCS$的問題，但是有一點變形。因此我們會先想到應該是$DP$，而可能會想到另外兩個狀態是:

1. 共同部分是不是目前兩個字串前綴的結尾
2. 最小的分段是幾段

也就是$:dp[i][j][end][k]=$最長長度，$end=0:$非結尾，$end=1:$是結尾
那麼我們就會發現轉移式$:dp[i][j][0][c]=$
$\max$$\begin{cases}
dp[i-1][j][1][c],\ dp[i-1][j][0][c]\
dp[i][j-1][1][c],\ dp[i][j-1][0][c]\
dp[i-1][j-1][1][c],\ dp[i-1][j-1][0][c]\
\end{cases}$
且如果$s[i]\neq t[j]:dp[i][j][1][c]=0$
如果$s[i]=t[j]:dp[i][j][1][c]=$
$\max{dp[i-1][j-1][1][c]+1,\ dp[i-1][j-1][0][c-1]+1}$

程式碼:

const int _n=1010;  
int n,m,k,dp[_n][_n][2][11];  
char s[_n],t[_n];  
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);  
  cin>>n>>m>>k>>(s+1)>>(t+1);  
  rep(i,0,m+1)rep(c,1,k+1)dp[0][i][0][c]=dp[0][i][1][c]=-1e5;  
  rep(i,0,n+1)rep(c,1,k+1)dp[i][0][0][c]=dp[i][0][1][c]=-1e5;  
  rep(i,1,n+1)rep(j,1,m+1)rep(c,1,k+1){  
    dp[i][j][0][c]=max(dp[i][j][0][c],dp[i-1][j][1][c]);  
    dp[i][j][0][c]=max(dp[i][j][0][c],dp[i-1][j][0][c]);  
    dp[i][j][0][c]=max(dp[i][j][0][c],dp[i][j-1][1][c]);  
    dp[i][j][0][c]=max(dp[i][j][0][c],dp[i][j-1][0][c]);  
    dp[i][j][0][c]=max(dp[i][j][0][c],dp[i-1][j-1][1][c]);  
    dp[i][j][0][c]=max(dp[i][j][0][c],dp[i-1][j-1][0][c]);  
    if(s[i]==t[j]){  
      dp[i][j][1][c]=max(dp[i][j][1][c],dp[i-1][j-1][1][c]+1);  
      dp[i][j][1][c]=max(dp[i][j][1][c],dp[i-1][j-1][0][c-1]+1);  
    }else dp[i][j][1][c]=0;  
  }ll maxx=0;rep(i,1,n+1)rep(j,1,m+1)rep(c,1,k+1){  
    maxx=max(maxx,max(dp[i][j][0][c],dp[i][j][1][c]));  
  }cout<<maxx<<'\n';  
  return 0;  
}  

標頭、模板請點Submission看
Submission