愛奇芸2018秋校招アルゴリズムエンジニア(第一場)C二乗列【区分+LCS】B乳牛番号【並べ替え】A括弧マッチング深さ【桟】

[プログラミング問題]二乗文字列時間制限:1秒空間制限:32768 Kもし一つの文字列Sが二つの文字列Tによって接続するならば、すなわちS=T+T、私たちはSを二乗文字列と呼んで、例えば","aabab","xxxx"はすべて二乗文字列である.牛には文字列sがあります.牛がsからできるだけ少ない文字を削除して、残りの文字列が平方列になるように手伝ってください.すなわち,sの最長男シーケンスを探し出し,このサブシーケンスは二乗列を構成する.入力説明:文字列s、文字列長length(1≦length≦50)を入力し、文字列には小文字のみが含まれます.
出力記述:正の整数、すなわち要求を満たす二乗列の長さを出力します.
入力例1:frankfurt
出力例1:4
分析:sの最長男シーケンスを探し出し、このサブシーケンスは二乗列を構成する.題意の中のこの言葉はもうかなりはっきりしている.現在の文字列を2つのサブ列に分割してLCSを行うだけでいいです.テーマのデータ範囲が極小なので、一番便利な書き方で書きました.

#include
#include
#include
#include
#include
#include
using namespace std;
string str, s1, s2;
int dp[55][55];
int LCS() {
    memset(dp, 0, sizeof(dp));
    int m = s1.length()-1;
    int n = s2.length()-1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}
int main()
{
    cin >> str;
    int len = str.length();
    str = " " + str;
    int ans = 0;
    for (int i = 1; i < len; i++) {
        s1 = " "; s2 = " ";
        for (int j = 1; j <= i; j++) s1 += str[j];
        for (int j = i + 1; j <= len; j++) s2 += str[j];
        ans = max(ans,LCS() * 2);
    }
    cout << ans << endl;
    return 0;
}

[プログラミング問題]乳牛番号時間制限:1秒空間制限:32768 K牛はn匹の乳牛を飼っており、牛は乳牛ごとに番号をつけたいと思っているので、簡単に見分けることができます.各乳牛は数字に好みがあり、i番目の乳牛は1とx[i]の間の整数(1とx[i]を含む)を望んでいる.牛はすべての乳牛の好みを満たす必要があります.牛が牛に何種類の乳牛番号を与える方法があるかを計算し、要求に合った番号付け方法の総数を出力するのを助けてください.入力記述:入力は2行を含み、第1行は1つの整数n(1≦n≦50)であり、乳牛の数を表す第2の挙動n個の整数x[i](1≦x[i]≦1000)である.
出力記述:牛がすべての乳牛の好みを満たす方法の数を表す整数を出力します.答えが大きい可能性があるので、出力方法数は100000007のモジュールです.
入力例1:4 4 4 4
出力例1:24
分析:牛1頭当たりの選択可能性を考慮する必要があります.一定数の番号は選択できません.選択機会の少ない牛に譲ったからです.だから順番を並べて解決しました.

#include
#include
#include
#include
#include
#include
using namespace std;
const long long int mod = 1e9 + 7;
int a[55];
int main()
{
    int n; long long int ans = 1;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
        (ans *= 1ll*(a[i] - i)) %= mod;
    }
    printf("%lld
", ans);
    return 0;
}

[プログラミング問題]カッコマッチング深さ
解析:クラシックなかっこマッチング、スタック解決、メンテナンス下Stack_kh.size();