python-解决圆 table session (ZCO，2012)

Question

N knights are sitting in a circle. Making a dessert for knight i costs C[i]. Find the minimum cost such that for every pair of adjacent knights, at least one gets his dessert. N ≤ 10 ** 6.

输入

There are 2 lines of input. The first line contains a single integer N, the number of seats at the table. The next line contains N space-separated integers, each being the cost of the dessert of a Knight, listed in counterclockwise order around the table.

输出

The output should be a single line containing a single integer, the minimum possible cost for you, the chef.

问题引用: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]))

Answer 1

这个问题的解决方案基本上必须处理 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] = 包含该元素的最佳答案。