백준 9251: LCS(DP)

https://www.acmicpc.net/board/view/28163

5시간동안 개삽질하고

답 5분 보고 어이없어서

멘탈터짐

unsigned int max(unsigned int first, unsigned int second)
{
    return first > second ? first : second;
}
 
unsigned int dp[1001][1001];
 
int main()
{
    std::string A, B;
    std::cin >> A >> B;
    for (int y = 1; y <= A.size(); ++y)
    {
        for (int x = 1; x <= B.size(); ++x)
        {
            if (A[y - 1] == B[x - 1])
                dp[y][x] += dp[y - 1][x - 1] + 1;
            else
                dp[y][x] = max(dp[y][x - 1], dp[y - 1][x]);
        }
    }
    for (int y = 0; y <= A.size(); ++y)
    {
        for (int x = 0; x <= B.size(); ++x)
        {
            std::cout << dp[y][x]; //dp[A.size()][B.size()]가 정답
        }
        std::cout << '\n';
    }
    return 0;
}
 

2차원배열을 이용하는 것도 참

생각도 못했다

걍 너무 내가 병신쪼다같고 막.. 그래....

unsigned int getlen(int it, unsigned int n)
{
    //KJFSDFLKDF
    int tmp = 1;
    int pos = n;
    for (unsigned int i = it; i < str1.size(); ++i)
    {
        //findPos = prePos;
        //KJSDFKSDFLKDFJS SKDJKFLSKDJFLKSDJF
        auto finder = str2.find(str1[i], pos);
        if (finder == std::string::npos) continue;
        if (dp2[finder] != 0 && dp2[finder] <= tmp) { ++pos; --i;  continue; }
        unsigned int j = finder;
        while (j < str2.size())
        {
            if (dp2[j] != 0) break;
            ++j;
            //if (tmp > dp2[j] && str2[j] == str1[i]) break;
        }
        if (tmp > dp2[j] && dp2[finder] != 0) { ++pos; --i;  continue; }
        if (j == str2.size())
        {
            dp2[finder] = ++tmp;
        }
        else
        {
            if (str1[i] == str2[j] && tmp < dp2[j]) continue;
            dp2[finder] = dp2[j];
            tmp = dp2[j];
            dp2[j] = 0;
        }
        //prePos = finder;
        //int jtmp = 0;
        //for (unsigned int j = i + 1; j < str1.size(); ++j)
        //{
        //    findPos = finder;
        //    finder = str2.find(str1[j], findPos);
        //    if(finder == std::string::npos) continue;
        //    ++jtmp;
        //    if (finder == str2.size() - 1) break;
        //}
        //cnt = cnt > tmp + jtmp ? cnt : tmp + jtmp;
    }
    std::cout << '\n';
    cnt = cnt > tmp ? cnt : tmp;
    for (int i = 0; i < str2.size(); ++i)
        std::cout << dp2[i] << ' ';
    return cnt;
}
 
int main()
{
    std::cin >> str1 >> str2;
    int dcnt = 0;
    for (unsigned int i = 0; i < str1.size(); ++i)
    {
        cnt = 0;
        auto startPoint = str2.find(str1[i]);
        if(startPoint == std::string::npos) continue;
        std::cout << str2[startPoint] << ' ';
        dp1[dcnt++] = getlen(i + 1, startPoint + 1);
    }
    std::sort(dp1, dp1 + str1.size());
    std::cout << dp1[str1.size() - 1];
    return 0;
}

똥꼬쑈의 흔적

결국 대패배