【kickstart2020 round D】前兩題python解題思路

因為招行夏令營沒有參加D輪，但事實是參加了依然是一題選手，無奈，在此總結前兩題python解題思路。

題目1 Record Breaker

解題思路：

字首max

代碼：

T=int(input())
for tt in range(T):
    N=int(input())
    num=[int(i) for i in input().split()]
    pre_max=[-1] # 此處注意不可以是0
    for i in range(N):
        pre_max.append(max(pre_max[-1],num[i]))
    ans=0
    for i in range(N):
        if i!=N-1:
            if num[i]>pre_max[i] and num[i]>num[i+1]:
                ans+=1
        else:
            if num[i]>pre_max[i]:
                ans+=1
    print('Case #{}: {}'.format(tt+1,ans))
           

題目2 Alien Piano

講真這道題我讀了特别多遍。。

解題思路：

1 DP

if (ar[i] > ar[i - 1])
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + ((j > k) ? 0 : 1));  # 若j<k 則需要一次violation
else if (ar[i] < ar[i - 1]) 
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + ((j < k) ? 0 : 1));  # 若j>k 則需要一次violation
else：
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j]);
if (j != k) 
    dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + 1);
# 若j！=k則需要一次violation                          
           

2 貪心

t = int(input())
 
for tt in range(T):
    n = int(input())
     
    up = 0
    down = 0
    violations = 0
     
    l = list(map(int,input().split()))
     
    for j in range(1,len(l)):
        if(l[j]==l[j-1]):
            continue
        if(l[j]>l[j-1]):
            up += 1
            down = 0
        else:
            down += 1
            up = 0
        if(up>3 or down>3):
            violations+=1
            up = 0
            down = 0
    print('Case #{}: {}'.format(tt+1,violations))