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

uiucpass 5년 전 0

역추적을 구현하였는데.. 계속 틀렸다고 나오네요 반례가 무엇인지 잘 모르겠습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>

using namespace std;

int lcs[1001][1001];
string a, b, ans;
stack<int> st;

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;
            }
            else{
                lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
            }
            // cout.width(5);
            // cout << DP1[j] << "       "
        }
    }

    int i = la;
    for(int j = lb; j != 0; j--){
        if(a[i- 1] == b[j - 1]){
            st.push(a[i - 1]); 
            i--;
        }
        else{
            if(lcs[i - 1][j] > lcs[i][j - 1]) i = i - 1;
            else ;
        }
    }

    cout << lcs[la][lb] << endl;
    while(st.size()) {
        cout << st.top();
        st.pop();
    }
    return 0;
}
	

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

문제

문제

출처

ICPC

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

uiucpass 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말