uvalive3608 (2점 + DP)

제목의 대의: a, b 두 개의 직렬을 제시하고 a열은 몇 개의 직렬로 나눌 수 있다. a의 각 분리된 직렬을 각각 b열로 전환시키고 가장 적은 조작수는 얼마냐고 묻는다.
사고방식: 2분의 답안, 시간 초과를 피한다.dp[i][j]는 a열의 i번째 문자와 j열의 j번째 문자가 가장 적은 조작수를 나타낸다.그러면 a의 i+1 문자와 b의 j+1 문자가 같을 때 가장 작은 조작수는 a에서 i까지의 문자와 b에서 j까지의 문자의 값이 같다.그러면 a에서 i 문자와 b에서 j + 1 문자가 될 때 가장 작은 조작수는 a에서 i 문자와 b에서 j 문자의 값 + 1일 수 있으며 같을 수 없습니다.그러면 a에서 i+1 문자와 b에서 j 문자가 될 때 이치는 같다.
코드:

#include 
using namespace std;
#include 
#include 

const int INF = 0x3f3f3f3f;
int n,m;
char a[5555],b[555];
int dp[5555][555];

bool check(int mid) {
    for(int i = 0; i <= n; i++)
        for(int  j = 0; j <= m; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for(int i = 0; i <= n; i++) {
        if(dp[i][m] <= mid)
            dp[i][0] = 0;
        for(int j = 0; j <= m; j++) {
            if(dp[i][j] > mid)
                continue;
            dp[i + 1][j + 1] = min(dp[i + 1][j + 1],dp[i][j] + (a[i + 1] == b[j + 1]?0:1));
            dp[i][j + 1] = min(dp[i][j + 1],dp[i][j] + 1);
            dp[i + 1][j] = min(dp[i + 1][j],dp[i][j] + 1);
        }
    }
    if(dp[n][m] <= mid)
        return true;
    return false;
}

int main() {

    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%s%s",b+1,a+1);
        n = strlen(a + 1);
        m = strlen(b + 1);
        int l = 0,r = max(n,m);
        while(l < r) {
            int mid = (l + r)/2;
            if(check(mid)) {
                r =  mid;
            }
            else
                l = mid + 1;
        }
        printf("%d
",l);
    }
    return 0;
}