代码之家 › 专栏 › 技术社区 › Chandramauli Chakraborty

python-求解圆桌(zco,2012)

dynamic-programming algorithm python

Chandramauli Chakraborty · 技术社区 · 6 年前

骑士们围成一圈。为骑士做甜点我要花C[I]。找到最小的成本,这样每对相邻的骑士,至少有一个得到他的甜点。N_10**6.

输入

有两行输入。第一行包含一个整数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 回复 | 直到 6 年前

Deepak Tatyaji Ahire 6 年前

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] );

}