codeforces 1425E, 10 000 простых вопросов

Всем привет, добро пожаловать в тему codeforces.

Сегодня мы выбрали вопрос E из игры codeforces 1425, которая представляет собой тренировочную игру ICPC, совместно организованную несколькими школами в Индонезии.формат АКМ, сложность аналогична. Сегодня мы выбрали один из вопросов средней сложности, из-за относительно небольшого количества участников по системе соревнований ACM прошло всего 157 человек. Но на самом деле трудность не велика, она близка к вопросу общей конкуренции.

Ссылка: https://codeforces.com/contest/1425/problem/E

Без лишних слов, давайте посмотрим на смысл вопроса.

смысл названия

Человек играет в игру активации ионов, фоном которой является энергетический переход ионов в смоделированной химии. В химии ионы поглощают энергию и могут переходить из состояния с низкой энергией в состояние с высокой энергией и выделять определенное количество энергии.

Теперь в ряд выстроены N ионов (индекс 1-N), каждый со своим энергетическим параметром. То есть сколько энергии может быть поглощено для прыжка, и сколько энергии высвободится после прыжка. Существует также особое свойство, что этиМежду ионами существует связь, отношение ассоциации по умолчанию таково, что i-й ион связан с i+1-м ионом. Когда ион i переходит, переход происходит, даже если ион i+1 не поглощает энергию. вИон N не может установить совместную связь.

Теперь, когда человек приобрел способность изменять связь между ионами в K раз, он долженСтрого изменить связанные объекты ионов K. Кроме того, мы можем свободно выбирать любое количество ионов для активации.Какую максимальную прибавку энергии мы можем получить? Прирост энергии – это полученная энергия минус затраченная энергия.

в, энергия, поглощаемая и выделяемая каждым ионом, меньше, чемположительное целое число .

Образец

Есть 3 строки ввода, первая строка — два целых числа N и K.

Вторая строка - N целых чисел, то есть энергия, высвобождаемая при переходе этих ионов N. Третья строка также содержит N целых чисел., - энергия, необходимая для этих переходов ионов N.

В примере мы будемСвязь 5 ионов меняется на 1 ион, активируя ион 5, так что мы можем заставить в общей сложности 1-5 ионов совершить переход. Полученный прирост энергии равен 5 + 6 + 7 + 8 + 10 - 1 = 35.

отвечать

Нет никакой идеи, чтобы получить его, мы можем начать думать с простой ситуации.

K=0

Сначала рассмотрим ситуацию, когда К=0, когда К=0, мыНевозможно изменить какую-либо совместную ситуацию. Когда мы выбираем i ионов для активации, все ионы с номерами больше i будут активированы из-за связанного с ними эффекта, и нам нужно только потратитьэнергия.

Этот случай очень прост, для i-го иона его выигрыш равен. здесьявляется константой, ипредставляет собой сумму последовательностей. Нам нужно только пройти его, чтобы найти i, который максимизирует прибыль.

После того, как мы проанализировали простейший случай K=0, мы обнаружили одну вещь, а именноВсе ионы непрерывны, за исключением иона, который мы заменяем ассоциированными ионами.. Когда мы активируем один, мы можем активировать серию.Это немного похоже на связанный список.Когда мы меняем ассоциацию ионов, мы фактически изменяем следующий указатель узла в связанном списке.

Например, когда мы смотрим на это изображение, когда связанный объект иона a меняется с a+1 на b, это фактически означает, что мы указываем следующий узел a на b. Итак, когда мы пересекаем, следующей позицией a является b.

Следующая позиция a произвольна, она может быть до или после a, но не может быть сама по себе. Если подумать об этом, то на самом деле так называемая модификация совместной связи ионов КИзменить K ребер в связанном списке. Затем мы можем выбрать количество начальных позиций для обхода связанного списка, чтобы максимизировать преимущества, указанные в вопросе.

Кроме того, мы обнаружили, что независимо от того, как соединены K ребер, содержимое, отличное от K ребер, все равно соединено последовательно. мы можем использоватьалгоритм суммы префиксовбыстро найти сумму определенного интервала.

алгоритм суммы префиксов

Алгоритм префиксной суммы очень прост, он подходит для быстрых решений для разных a и b без изменения самого массиваПроблема.

На самом деле метод очень простой, и это даже не структура данных. Нам нужен только массив для завершения, мы подаем заявку на новый массив, называемый presum. мы надеемся, то естьpresum[i] равно сумме первых i чисел в массиве A. Таким образом, мы можем получить.

И нам также очень просто поддерживать презумпцию, где презум[1] = А[1], для всех i > 1 имеет место презум[i]=предсумма[i-1] + A[i]. С помощью такой простой рекурсии мы можем легко найти все предположения и вычислить все суммы префиксов.

Префикс сумма очень удобен и используется во многих темах, но есть небольшое условие, чтоЭлементы в массиве, которые поддерживают сумму интервалов, не могут измениться. В противном случае его нельзя использовать.

K >= 2

Поговорив о сумме префиксов, продолжим анализ задачи и рассмотрим ситуацию, когда К >= 2. Мы можем найти, что при K > 2 мыВсе ионы могут быть получены до тех пор, пока i меньше N активировано.

Давайте рассмотрим пример, это случай, когда K=2:

Мы активировали определенный i, затем перескочили на 1 в позиции и перескочили на a+1 в i-1. Хотя мы прыгнули дважды, все ионы не были потрачены впустую.

Используя идею рекурсии, мы можем найти, что пока K >= 2, все ионы гарантированно попадают в капсулу. Таким образом, мы можем легко найтиНам просто нужно выбрать i с наименьшей стоимостью.

Давайте запишем эту ситуацию и назовем ее ситуацией 1,Дело 1Да:

Многие люди случайно пропускают его, когда анализируют K >= 2, и здесь его легко проигнорировать.Есть предпосылки для установления дела 1, предпосылка состоит в том, что активированный ион, который мы выбираем, не может быть последним, потому что последний ион не связан. Весьма вероятно, что стоимость первых ионов N-1 больше, чем прирост, и только прирост N-го иона положителен. Нам нужно специально судить об этом случае, то есть активировать N-й ион. Поскольку у него нет связанного объекта, мы можем активировать только один ион. ЭтоСлучай 2, получается:.

K = 1

Зачем ставить случай K=1 в конец? Потому что он самый сложный, ситуаций много, и его очень и очень легко пропустить.

Как мы упоминали ранее, для позиции i связанный с ней объект может находиться либо перед ней, либо позади нее. Нам нужно разобрать эти два случая отдельно, в первую очередьсвязанный с ним объект предшествует ему. Тогда оптимальной ситуацией должно быть то, что он связан с ионом № 1. Таким образом, пока мы активируем любой ион в интервале [2, i], мы можем получить общий доход первых i ионов. Но вот другой вопрос, хотим ли мы снова активировать ион i+1? При активации мы получаем пользу от всех ионов, или нет.

Таким образом, мы получаем еще два случая, случай 3 и случай 4. Перечислим также, дляСлучай 3, мы можем получить все преимущества первых i ионов, а стоимость будет наименьшей среди первых i ионов, где чем больше i, тем лучше, а максимум равен N-1. Это написано как:. Случай 4 заключается в активации иона i+1 на основе случая 3,Случай 4:, мы снова проанализируем его и обнаружим, что мы можем выбрать i так, чтобы D[i+1] было как можно меньше,Достаточно маленький, чтобы стать предпоследним по величине в мире.

Мы видели положение стыка и нескольких узлов спереди, а потом посмотрим, какое положение стыка будет сзади, или посмотрите на эту картинку:

Мы видим, что точка a связана с точкой b после нее.На данный момент у нас также есть два случая.Первый случай состоит в том, чтобы активировать только 1. В этом случае мы можем получить интервал, отличный от [a+1,b -1] значение внутри. Второй случай — активировать a+1 после активации 1, чтобы мы также могли получить все ионы, но это стоит A[1] и A[a+1].

Это только поверхностный анализ, когда мы проанализируем его глубже, мы обнаружим, что энергия, выделяемая ионом, должна быть положительным числом. Мы, конечно, надеемся, что чем меньший интервал он пропускает, тем лучше, потому что слишком большой пропуск — это потеря. Самый крайний случай должен быть b=a+2, то есть мыПропустить только элемент a+1. Есть два случая пропуска элемента a+1.Первый случай true jumping, что означает, что это значение отбрасывается.Второй случай false jumping.Хоть мы и пропускаем его, но все равно активируем его искусственно.

Давайте разберемся, чтобы получить случай 5 и случай 6,Случай 5да.Случай 6Да, хотя мы и пропускаем +1, мы все равно активируем его, поэтому результат должен быть.

Мы тут разобрали, там уже 6 ситуаций, как думаете, закончилось? Неправильно, на самом деле есть еще одна ключевая ситуация, которую мы упустили из виду. этоУзел № 1 вместе с N узлами, а затем начните с узла № 2, чтобы найти самый прибыльный узел для активации. Это последний случай, т.Случай 7, который записывается как:.

Да, вы правильно прочитали, этот вопросВсего 7 ситуаций, без одной нет выхода на АС. Хотя вопрос простой, нам нелегко понять все 7 ситуаций одновременно, когда мы задаем вопрос, но такие вопросы нам более полезны, потому что они действительно тренируют наше мышление, и это полезно. очень важно для совершенствования Утонченность нашего мышления очень полезна.

Наконец, мы прикрепляем код.

import sys
n, k = list(map(int, input().split(' ')))


activate = list(map(int, input().split(' ')))
deactivate = list(map(int, input().split(' ')))

presum = [0 for _ in range(n+2)]

for i in range(1, n+1):
    presum[i] = presum[i-1] + activate[i-1]

ret = 0

if k == 0:
    for i in range(1, n+1):
        # 情况0，不需要考虑连带
        ret = max(ret, presum[n] - presum[i-1] - deactivate[i-1])
elif k == 1:
    for i in range(1, n):
        # 情况3 n-1连1
        ret = max(ret, presum[n-1] - deactivate[i-1])
    
    # 情况3再加上第N个离子
    if deactivate[n-1] < activate[n-1]:
        ret += (activate[n-1] - deactivate[n-1])

    deac = sorted(deactivate[1:n-1])
    ac = sorted(activate[1:n-1])

    # 情况5，激活1，跳过1个节点
    ret = max(ret, presum[n] - deactivate[0] - ac[0])
    # 情况6 激活1，跳过1个节点后，再激活
    ret = max(ret, presum[n] - deactivate[0] - deac[0])
    # 情况4 
    ret = max(ret, presum[n] - deac[0] - deac[1])

    # 情况7 1连n，激活i
    for i in range(2, n+1):
        ret = max(ret, presum[n] - presum[i-1] - deactivate[i-1])
else:
    # 情况1
    for i in range(1, n):
        ret = max(ret, presum[n] - deactivate[i-1])   

    # 情况2
    ret = max(ret, activate[n-1] - deactivate[n-1])

print(ret)

Этот вопрос немного утомляет. Возможно, вам будет трудно полностью понять его, основываясь на том, что я сказал. Рекомендуется взять больше бумаги и карандаша, чтобы нарисовать картинку, которая поможет вам думать.

Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)

В этой статье используетсяmdniceнабор текста

Оригинальная ссылка, обратите внимание