Обмен технологиями

한어Русский язык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 Всё. Затем основная идея состоит в том, чтобы перебрать метод перебора, найти разницу в прибыли каждой группы и вернуть максимальное значение. После попытки выяснилось, что двухуровневый метод истекает по тайм-ауту, и эта проблема ограничивается. 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] как предполагаемого минимального значения для сравнения и обновления обхода, а затем определите maxSub для представления максимального отличия от minval при переходе к позиции i. , что стоит Обратите внимание, что при обходе обратите внимание на порядок 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. Идеи

Прочитав вопрос, вы узнаете, сколько всего путей можно пройти из точки А в точку Б по определенным правилам. При анализе вопроса нужно знать, что по определенным правилам можно идти вправо или вниз, что наводит на мысль о динамическом программировании дп. На что еще нужно обратить внимание в вопросе, так это на то, что контрольная точка. коня нельзя переместить (посетить), то есть коня в шахматах. Точки, обозначенные диагональным «солнцем» на координатах, включая начальную точку коня, называются контрольными точками. Среди них лошадь — это фиксированная точка (x, y), заданная вначале, и вопрос также определяет связь между точкой прыжка лошади и ее отправной точкой. Кроме того, следует отметить, что согласно примеру и шахматной доске размер шахматной доски равен (n+1)(м+1)。
Таким образом, на основании вышеизложенного анализа можно сделать вывод, что:
(1) Вы можете использовать идеи динамического программирования для решения проблем;
(2) Контрольная точка лошади, помимо диагонального «солнца», включает в себя и ее собственную стартовую позицию;
(3) Размер шахматной доски равен (n+1).(м+1).
Поэтому, после анализа точек внимания, мы возвращаемся к представлению состояния dp и уравнению перехода состояний динамического программирования;
Основываясь на общих правилах темы, состояние dp[i][j] определяется как следующее: существует не более нескольких путей к этой позиции;
Выведите уравнение перехода состояний: dp[i][j] = d[i][j-1] + d[i-1][j];
Кроме того, обратите внимание, что если исходное положение точки Б совпадает со стартовым положением лошади или контрольной точкой, а верхняя и левая часть точки Б все заблокированы, то есть контрольной точки, то в приведенном выше крайнем случае , в это время dp[i][j] = 0. Следующий шаг — реализация программы.

3.3 Реализация Программы – дп.

Сначала напишите входные данные в соответствии с анализом идеи, определите и откройте массив dp (о двух подводных камнях речь пойдет позже), а также в соответствии с размером шахматной доски, чтобы иметь возможность равномерно описывать координаты, дополнительно Здесь будут открыты строка и столбец, затем необходимо сопоставить x и y. Просто установите координаты +=1, затем изучите проблему инициализации dp и нарисуйте картинку, чтобы было понятнее:

Затем фактический двумерный массив просматривается от [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];
а. Определить экстремальные ситуации: 1. Контрольная точка лошади блокирует путь 2. Задача совпадений;
б. Уравнение перехода состояния нормального выполнения: dp[i][j] = d[i][j-1] + d[i-1][j];
(4), наконец, выведите dp[n+1][m+1].
Кроме того, две упомянутые выше ловушки заключаются в том, что после того, как я закончил писать, отправка не удалась, и я обнаружил, что данные выходят за пределы допустимого диапазона, поэтому для открытия массива лучше всего использовать long long. Еще одна ловушка заключается в том, что диапазон размеров. проем слишком велик. Используется первый этаж, поэтому он должен быть как минимум больше или равен 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] Переход через реку Пешка