# hbr

# LCS problem
https://www.udebug.com/UVa/10192
:::spoiler Vacation

#include <bits/stdc++.h>

using namespace std;

int LCS(const string &A, const string &B)
{
    vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));

    for (int i{1}; i <= A.size(); ++i)
        for (int j{1}; j <= B.size(); ++j)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (A[i - 1] == B[j - 1])
                dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
        }

    return dp[A.size()][B.size()];
}

int main()
{
    string input;
    vector<string> a;
    vector<string> b;
    getline(cin, input);
    int num = 0;
    while (input != "#")
    {
        a.push_back(input);
        getline(cin, input);
        b.push_back(input);
        getline(cin, input);
        num++;
    }
    for (int i = 0; i < num; i++)
    {
        int count = LCS(a[i], b[i]);
        cout << "Case #" << i + 1 << ": you can visit at most " << count << " cities.\n";
    }
}

:::

# Greedy Problem

:::spoiler 貪婪之糊 (未完成)

// https://zerojudge.tw/ShowProblem?problemid=d652
// d652: 貪婪之糊
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    int total = 1;
    while (a.size() >= 2)
    {
        int minProduct = a[0] * a[1] * a[2];
        int index = 0;
        for (int i = 0; i < a.size() - 2; i++)
        {
            int p = a[i] * a[i + 1] * a[i + 2];
            if (p < minProduct)
            {
                minProduct = min(p, minProduct);
                index = i + 1;
            }
        }
        a.erase(a.begin() + index);
        total *= minProduct;
    }
    cout << total;
}

:::