글 읽기 - 계속 틀렸습니다가 뜨는 데 반례가 무엇이 있을까요?

uiucpass 5년 전 0

각 배열자리에 LCS의 길이에 맞춰 common sequence string을 삽입하면서 구했습니다.

게시판에 있는 반례를 다 넣어보긴 했는데 케이스가 워낙 작아서 무엇이 문제인지 잘 모르겠습니다.

도와주시면 정말 감사하겠습니다.

#include <iostream>
#include <string>

using namespace std;

int lcs[1001][1001];
string DP1[1001], DP2[1001];
string a, b;

int main() {
    cin >> a >> b;
    int la = a.length(), lb = b.length();

    for(int i = 1; i <= la; i++){
        for(int j = 1; j <= lb; j++){
            if(a[i - 1] == b[j -1]){
                lcs[i][j] = lcs[i - 1][j - 1] + 1;
                DP2[j] = DP1[j - 1];
                if(DP2[j].length() < i) DP2[j].push_back(a[i - 1]);
            }
            else{
                if(lcs[i - 1][j] < lcs[i][j - 1]){
                    lcs[i][j] = lcs[i][j - 1];
                    DP2[j] = DP2[j - 1];
                }
                else{
                    lcs[i][j] = lcs[i - 1][j];
                    DP2[j] = DP1[j];
                }
            }
            // cout.width(5);
            // cout << DP1[j] << "       "
        }
        copy(DP2, DP2 + 1000, DP1);
        
    }

    cout << lcs[la][lb] << endl;
    cout << DP1[la];

    return 0;
}
	

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

계속 틀렸습니다가 뜨는 데 반례가 무엇이 있을까요?

uiucpass 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말