기술나눔

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

오늘의 질문 요약-day010

1. 가장 긴 회문 부분 문자열

1.1. 질문

1.2. 아이디어

질문을 읽은 후 길이가 n인 문자열에서 가장 긴 회문 부분 문자열의 길이를 찾는다는 것을 알 수 있습니다. 회문 부분 문자열은 대칭 문자열로 이해될 수 있습니다. 대칭성 때문에 기본 개념은 "중심 확장 방법"입니다. 즉, 문자열을 순차적으로 탐색한 다음 문자의 양쪽으로 확장하는 것입니다. retlen 변수에 기록됩니다. 탐색 후 마침내 최대 길이를 반환합니다. 이해를 돕기 위해 그림을 그려보세요.

또한, 예제를 분석할 때 홀수와 짝수의 차이에도 주의해야 하므로 다음 단계는 프로그램 구현이다.

1.3. 프로그램 구현

먼저, 아이디어 분석의 "중심 확장 방법"에 따르면 문자열은 i에서 중앙 스테이션으로 이동하여 확장되고, 차례로 얻은 retlen은 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계층이 시간 초과되는 것으로 확인되었으며 이 문제는 다음으로 제한됩니다. 해결하는 데 1ms가 걸립니다. 그러므로 무차별 방식을 기반으로 한 최적화가 필요하므로 무차별 대입 방식도 작성합니다. 그러다가 무차별 방식을 기반으로 역추적, 최적화, 사고 및 발견을 너무 많이 반복했습니다. reverse, 먼저 매도를 고려한다. 그러면 매도점 이전의 최소값만 구하면 되고, 얻은 차이가 최대차이가 된다. 즉, 한 번만 순회하면 된다는 뜻이다. 다음 단계는 프로그램 구현이다.

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 배열을 정의하고 오픈하며(두 가지 함정은 나중에 논의), 체스판의 크기에 따라 좌표를 균일하게 기술할 수 있도록 추가로 행과 열이 여기에서 열리면 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을 초기화합니다(레이어를 하나 더 엽니다).
(3) [1, n+1]과 [1, m+1]의 경계 제어 순회에 주의하면서 두 자리 배열을 순회합니다.
a. 극단적인 상황을 결정합니다: 1. 말의 제어점이 경로를 차단합니다. 2. 우연의 문제;
b. 정상 실행 상태 천이 방정식: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), 최종적으로 dp[n+1][m+1]을 출력한다.
게다가 위에서 언급한 두 가지 함정은 작성을 마친 후 제출이 실패하고 데이터가 범위를 벗어났다는 것을 발견했기 때문에 배열을 열려면 long long을 사용하는 것이 가장 좋습니다. 개구부가 너무 큽니다. 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 대중화그룹] 강을 건너다 폰