python- Решающий Круглый Стол (ZCO, 2012) - PullRequest
Новая
       75

python- Решающий Круглый Стол (ZCO, 2012)

0 голосов
/ 09 июня 2018

N рыцарей сидят в кругу.Приготовление десерта для рыцаря стоит C [i].Найдите минимальную стоимость, чтобы на каждую пару соседних рыцарей хотя бы один получал свой десерт.N ≤ 10 ** 6.

Вход

Есть 2 строки ввода.В первой строке записано единственное целое число N, количество мест за столом.Следующая строка содержит N разделенных пробелом целых чисел, каждое из которых представляет собой стоимость десерта Рыцаря, перечисленных в порядке против часовой стрелки вокруг стола.

Выходные данные

Выходные данныедолжна быть одна строка, содержащая одно целое число, минимально возможные затраты для вас, шеф-повара.

Ссылка на проблему: https://www.codechef.com/ZCOPRAC/problems/ZCO12004. Я пробовал это с помощью DP, мой код 

n=int(input())
a=[int(i) for i in input().split()]
def ram(x):
 m=x[0]
 k=0
 for i in range(2,n):
  if k==0:
    m+=min(x[i],x[i-1])
    if min(x[i],x[i-1]) ==x[i]:
     k=1
    else:
     k=0 
  else:
    k=0 
    continue
 return m 
b1=ram(a)
a.insert(0,a[n-1])
a.pop(n)
b2=ram(a)
print(min(b1,b2))

Но, к сожалению, это неправильный ответ, пожалуйста, найдите ошибку. Рекомендуется учитывать сложность времени, не превышающую 1 сек.редактировать: 

n=int(input())
a=[int(i) for i in input().split()]
cost1=cost2=[]
if n==1:
 print(a[0])
elif n==2:
 print(min(a[0],a[1]))
else:
 cost1.append(a[0])
 cost1.append(a[1])
 for j in range(2,n):
  cost1.append(a[j]+min(cost1[j-1],cost1[j-2]))
 cost2.append(a[n-1])
 cost2.append(a[n-2])
 for k in range(2,n):
  cost2.append(a[n-k-1]+min(cost2[k-1],cost2[k-2]))
 print(min(cost1[n-1],cost2[n-1]))

1 Ответ

0 голосов
/ 09 июня 2018

Это решение этой проблемы в основном должно учитывать 2 состояния.

Предположим, что вы в настоящее время находитесь в индексе i.Теперь вам нужно решить, хотите ли вы выбрать элемент индекса i в вашей окончательной сумме.

Состояния следующие:

1) Если вы решите, что элемент по индексу i должен быть включен в итоговую сумму, то не имеет значения, что этот элемент по предыдущему индексу, т.е. i-1, включен или нет.

2) Если вы решите, что элемент с индексом i не должен быть включен в итоговую сумму, то обязательно, чтобы элемент с предыдущим индексом, т.е. i-1, был включен.

В вашем решении вы заботитесь только о состоянии 1, но не о состоянии 2. Таким образом, вам нужно будет поддерживать 2 переменные для оптимальных промежуточных ответов по каждому индексу.

Вот примеркод: 

function calculate(int arr[], int start, int end){

    dp[start][0] = arr[start];
    dp[start][1] = 0LL;

    for(int i=start+1;i<=end;i++){

        dp[i][1] = dp[i-1][0];  //State 2

        dp[i][0] = arr[i] + min( dp[i-1][1], dp[i-1][0] ); //State 1

    }

    return min( dp[end][0], dp[end][1] );

}

Примечание: массив dp - это двумерный массив, в котором хранятся промежуточные оптимальные ответы.

dp [i] [1] = оптимальный ответ без включения элемента.

dp [i] [0] = Оптимальный ответ при включении элемента.

...