HZAU 교전 F 문제 LCS(dp)


17: LCS Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 170  Solved: 33 [Submit][Status][Web Board] Description
   Giving two strings consists of only lowercase letters, find the LCS(Longest Common Subsequence) whose all partition are not less than k in length. Input
There are multiple test cases. In each test case, each of the first two lines is a string(length is less than 2100). The third line is a positive integer k. The input will end by EOF. Output     For each test case, output the length of the two strings’ LCS.
Sample Input abxccdef abcxcdef 3 abccdef abcdef 3 Sample Output 4 6 HINT
   In the first test case, the answer is:
      abxccdef
      abcxcdef
    The length is 4.
   In the second test case, the answer is:
      abccdef
      abc def
   The length is 6 Source
제목: 두 문자열 안의 LCS를 구하십시오. 이 LCS의 모든 문자열 안의 분할 길이는 k보다 커야 합니다
문제풀이: LCS의 분할 길이가 k보다 크다는 것은 무엇입니까? 두 열 중에서 길이가 k보다 큰 것과 같은 겹치지 않는 하위 열을 찾아서 길이를 합치면 됩니다.
일반적인 LCS는 n^2의 이동이지만 연속하지 않을 수 있습니다. 이 단락은 최소한 k와 연속해야 합니다.
우리 역시 상태 dp[i][j]를 설정하여 a[i], b[j]에 도달하기 위해 이 제목이 요구하는 LCS는 얼마입니까
하면, 만약, 만약...b[j], dp[i][j]=max(dp[i-1][j], dp[i][j-1]), 이것은 문제가 없다. 만약에 a[i]==b[j]라면, 이것은 이것을 똑같이 가져갈까 말까 고려해야 한다. 만약에 앞과 똑같이 가져가지 않으면 앞으로 적어도 k개를 연속해야 한다. 처음에 내가 생각한 n^3의 방법은 앞으로 k개를 찾는 것이다. 그러나 이렇게 하면 믿을 수 없다. TLE는 틀림없다.
그래서 a[i]b[j]가 앞으로 몇 개 있는지 미리 처리해야 한다. f[i][j]라고 적고 이 O(n^2)를 미리 처리하면 된다. 그리고 만약에 a[i]==b[j], 그리고 f[i][j]>=k일 때 너는 k개를 연속으로 뽑을 수도 있고 f[i][j]개를 연속으로 뽑을 수도 있다. 왜냐하면 만약에 네가 k+1개, k>1을 연속으로 뽑으면 앞에 연속된 불만이 k개를 뽑으면 바로 0개를 뽑을 수 있다. 그래서 너는 0을 필요가 있다.그러나 앞에 있는 f[i][j]개는 연속으로 뽑을 필요가 없고 k개를 뽑으면 더 풀릴 수 있기 때문에 k개를 뽑을 수 있기 때문에 dp[i][j]=max(max(dp[i-1][j], dp[i][j-1]), max(dp[i-k][j-k]+k, dp[i-f[i][j]]][j]]][j]]]]][j]]]+f[j]]])로 옮길 수 있다.

#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;
#define   MAX           2105
#define   MAXN          1000005
#define   maxnode       10
#define   sigma_size    2
#define   lson          l,m,rt<<1
#define   rson          m+1,r,rt<<1|1
#define   lrt           rt<<1
#define   rrt           rt<<1|1
#define   middle        int m=(r+l)>>1
#define   LL            long long
#define   ull           unsigned long long
#define   mem(x,v)      memset(x,v,sizeof(x))
#define   lowbit(x)     (x&-x)
#define   pii           pair<int,int>
#define   bits(a)       __builtin_popcount(a)
#define   mk            make_pair
#define   limit         10000

//const int    prime = 999983;
const int    INF   = 0x3f3f3f3f;
const LL     INFF  = 0x3f3f;
const double pi    = acos(-1.0);
const double inf   = 1e18;
const double eps   = 1e-9;
const LL     mod   = 1e9+7;
const ull    mxx   = 1333331;

/*****************************************************/
inline void RI(int &x) {
      char c;
      while((c=getchar())<'0' || c>'9');
      x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
}
/*****************************************************/

char a[MAX],b[MAX];
int dp[MAX][MAX];
int f[MAX][MAX];

int main(){
    //freopen("in.txt","r",stdin);
    int k;
    while(~scanf("%s%s%d",a+1,b+1,&k)){
        int n=strlen(a+1),m=strlen(b+1);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a[i]==b[j]){
                    f[i][j]=f[i-1][j-1]+1;
                }
                else f[i][j]=0;
            }
        }
        mem(dp,0);
        for(int i=k;i<=n;i++){
            for(int j=k;j<=m;j++){
                if(f[i][j]>=k){
                    dp[i][j]=max(max(dp[i-1][j],dp[i][j-1]),max(dp[i-f[i][j]][j-f[i][j]]+f[i][j],dp[i-k][j-k]+k));
                }
                else{
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                }
                //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}