kkw564   1년 전

kmp와 dp를 이용하여 문제를 풀어나가려 했습니다.


dp를 다음과 같이 설정했습니다.

dp[i] :: i번째 일때 최대 문자열을 붙인 길이


for (int i = 0; i < vc.size(); i++)
{
int start = vc[i].first.first;
int end = vc[i].first.second;
int size = vc[i].second;

dp[end + 1] = max(dp[end + 1], dp[end - size + 1] + size);
}


이렇게 구성하며 dp를 구성해나갔는데 반례를 못찾겠습니다.

제가 문자열을 잘 붙여나갈 수 있도록 도와주실 분을 구합니다.. 도와주세요..


smu201111192   1년 전



반례입니다.

 aabbbbbbbbaa

 2

 aa

 cc




kkw564   1년 전

문제 이해를 잘못했네요 감사합니다!

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