技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

今日の質問まとめ-day010

1. 最長の回文部分文字列

1.1. 質問

1.2. アイデア

質問を読むと、長さ n の文字列内で最も長い回文部分文字列の長さを見つけることがわかります。回文部分文字列は対称文字列として理解できます。対称性のため、基本的な考え方は「中央展開方式」です。つまり、文字列を順番に走査し、両側の文字が等しい場合に文字の両側に展開されます。 retlen 変数に記録されます。トラバース後、最終的に最大長を返します。理解を容易にするために、図を描きます。

また、例を分析する際には奇数と偶数の違いにも注意する必要があるため、次のステップはプログラムの実装です。

1.3. プログラムの実施

まず、アイデア分析の「中心拡張法」に従って、i の中心ステーションから文字列をたどって拡張します。次に、奇数と奇数を区別する必要があるため、retlen と比較して更新します。それぞれ数値と偶数の最大値を見つけて、最後にそれを比較して最終的な最大値 retlen を取得し、それを返します。

class Solution
{
public:
    int getLongestPalindrome(string A)
    {
        size_t len = A.size();
        int left = 0;
        int right = 0;
        int retlen = 0;
        //偶数
        for(int i = 0;i < len; i++)
        {
            left = i;
            right = i + 1;
            while(left >= 0 && right < len && A[left] == A[right])
            {
                left--;
                right++;
            }
            retlen = max(retlen ,right - left - 1);
        }
        //奇数
        for(int j = 0;j < len;j++)
        {
            left = j;
            right = j;
            while(left >= 0 && right < len && A[left] == A[right])
            {
                left--;
                right++;
            }
            retlen = max(retlen ,right - left - 1);
        }
        return retlen ;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

2. 株式を売買するのに最適な時期 (1)

2.1. 質問

2.2. アイデア

質問を読むと、株式グループの売買の仕組みでは、売買は一度しかできないことがわかります。いつ売買しても損失が発生する場合、最大の利益が得られることを確認しましょう。損失が大きい、つまり利益がない場合、出力は 0 です。次に、基本的な考え方は、列挙/総当たり法を実行し、各グループの利益の差を求め、最大値を返すことです。試してみると、2 層の for がタイムアウトすることがわかり、この問題は に限定されます。解くのに1ミリ秒。したがって、総当たり法に基づいて最適化する必要があるので、総当たり法も書かれています。そして、総当たり法に基づいて、最適化、思考、発見というバックトラックを何度も繰り返しています。逆に、最初に売りを検討します。その後、売りポイントの前の最小値を見つけるだけでよく、得られた差が最大の差になります。つまり、それを 1 回トラバースするだけで済みます。次のステップはプログラムの実装です。

2.3. プログラムの実施

まず、総当たり法分析に従って、最大の差分出力を見つけるためにすべての状況が列挙されます。この質問はタイムアウトになります。したがって、最適化する必要があります。

#include <iostream>
using namespace std;

const int N = 1e5 +10;

int arr[N];

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

    int maxval = 0;
    for(int i = 0;i < n; i++)
    {
        for(int j = i;j < n;j++)
        {
            maxval = max(maxval , arr[j]- arr[i]);
        }
    }

    cout << maxval << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.4. プログラムの実装 – 最適化

上記の総当り手法に基づいて最適化を実行し、それを完全に理解するために、アイデア分析に基づいて実証図を作成します。

次にプログラムを実装するには、必要に応じて入力を記述し、minval を定義して arr[0] をトラバーサルの比較と更新の想定される最小値として初期化し、次に i 位置にトラバースするときの minval との最大差を表す maxSub を定義します。トラバースするときは、minval と maxSub の順序に注意してください。まず最小値 minval を見つけてから、maxSub を見つけます。

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
    int n = 0;
    cin >> n;
    vector<int> arr(n);
    int m = 0;
    while(n--)
    {
        cin >> arr[m];
        m++;
    }
    int minval = arr[0];
    int submax = 0;
    for(int i = 0;i<arr.size();i++)
    {
        minval = min(arr[i],minval);
        submax = max(submax, arr[i] - minval);
    }
    cout << submax << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3. 【NOIP2002普及団体】ポーン川を渡る

3.1. 質問

3.2. アイデア

問題を読むと、特定のルールに従って点 A から点 B に移動する経路が最大で何本あるかがわかります。質問を分析するときは、特定のルールに従って右または下に進むことができることを知っておく必要があります。これにより、動的計画法 dp のアイデアが浮かび上がります。また、質問で注意する必要があるのは、制御点です。馬の移動（訪問）はできません。つまり、チェスの騎士です。 馬の開始点を含む、座標上の斜めの「太陽」によって設計された点は、コントロールポイントと呼ばれます。このうち、馬は最初に与えられた固定点(x,y)であり、馬のジャンプ点と馬のスタート点の関係も出題されます。さらに、この例とチェス盤によれば、チェス盤のサイズは (n+1) であることに注意してください。(m+1)。
したがって、上記の分析に基づいて、次のように結論付けることができます。
(1) 動的プログラミングの dp アイデアを使用して問題を解決できます。
(2) 馬のコントロール ポイントには、斜めの「太陽」に加えて、独自の開始位置も含まれます。
(3) チェス盤のサイズは (n+1) です。（m+1）。
したがって、注目点を分析した後、動的計画法の dp 状態表現と状態遷移方程式に戻ります。
トピックのウォーキング ルールに基づいて、dp[i][j] 状態は次のことを表すように定義されます。この位置へのパスは最大でいくつかあります。
状態遷移方程式を導出します: dp[i][j] = d[i][j-1] + d[i-1][j];
なお、点Bの開始位置が馬やコントロールポイントの開始位置と一致しており、点Bの上と左がすべて塞がれている、つまりコントロールポイントの場合は、上記の極端な場合に注意してください。 , このとき dp[i] [j] = 0; 次にプログラムの実装です。

3.3. プログラムの実装 – dp

まず、アイデアの分析に従って入力を書き込み、dp 配列を定義して開きます (2 つの落とし穴については後で説明します)。また、チェス盤のサイズに従って、座標を均一に記述できるようにするために、追加のここで行と列が開かれ、次に x と y をマップする必要があります。座標 +=1 を設定してから、dp の初期化問題を調べて、より明確にするために図を描きます。

その後、実際の 2 次元配列を [1, n+1] と [1, m+1] からたどって、常に極限状況の処理を判断し、最終的に dp[n+1][m+1] を出力します。この時点では、このアイデアに問題はありません。手順の概要は次のとおりです。
(1)、x と y の座標をマッピングします。
(2) 配列定義に従って dp[0][1] = 1 または dp[1][0] = 1 を初期化します (もう 1 つのレイヤーを開きます)。
(3) [1, n+1] と [1, m+1] からの境界制御のトラバースに注意して、2 桁の配列をトラバースします。
a. 極端な状況を判断します。 1. 馬のコントロール ポイントが進路をブロックします。 2. 偶然の問題。
b. 通常の実行状態遷移方程式: dp[i][j] = d[i][j-1] + d[i-1][j];
(4)、最後に dp[n+1][m+1] を出力します。
さらに、上記の 2 つの落とし穴は、書き込みが完了した後に送信に失敗し、データが範囲外であることが判明したため、配列を開くには Long Long を使用するのが最善であることです。もう 1 つの落とし穴は、配列のサイズ範囲であることです。開口部が大きすぎるため、1 階が使用されるため、少なくとも 22 以上でなければなりません。以前は、dp[21][21] を使用してもすべてのユースケースに合格できませんでした。

#include <iostream>
using namespace std;

long long dp[22][22];

int main()
{
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    //映射坐标
    x += 1;
    y += 1;
    //初始化
    dp[0][1] = 1;
    //遍历
    for(int i = 1;i <= n+1; i++)
    {
        for(int j = 1;j <= m+1; j++)
        {
            //极端情况的处理:  1.马控制点 2.自身重合
            if((i != x && j != y && abs(i - x) + abs(j - y) == 3) || (i == x && j == y))
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
    }
    cout << dp[n+1][m+1] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

4. 質問リンク

最長の回文部分文字列
株を売買するのに最適な時期 (1)
【NOIP2002普及会】ポーン川を渡る