Kickstart2020 RoundA: Plates

2020 라운드A의 플래티스 문제를 시행해 봤다.
설치된 것은 여기.에 있습니다.

문제 요약

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d40bb
N개의 스택에는 각각 K개의 접시가 있고 접시마다 정수(beauty value)라고 쓰여 있다.여기서 P개의 접시를 꺼내면 그것과 최대치를 추구하고 싶은 문제에 대해.

알고리즘 1(TLE)

N개의 스택에서 접시를 꺼내는 모든 모드를 고려하면 이 모드에서 꺼낸 수량이 P개인 조합을 대상으로 화합의 최대치를 구하면 문제를 해결할 수 있다.
이때 모든 모드에는 스택 1에서 K를 꺼내는 조합이 있습니다. 각각 스택 2에서 K를 꺼내고 스택 3에서 K를 꺼내는 조합이 있습니다.마지막 스택 N까지 K개를 꺼낼 때의 조합으로 열거할 수 있기 때문에 K^N 같은 조합이 있습니다.
이 알고리즘에서 Testset1은 1\leqN\leq3이므로 패스할 수 있지만 1\leqN\leq50의 Test set2는 TLE이다.(1\leq K\leq 30)

알고리즘 2(Passed)

최종적으로 추구하고 싶은 것은 N 개의 창고에서 P 개의 접시를 꺼낼 때의 최대치입니다. 중도 상태를 고려해 보세요.제\rm{i}개 창고에서\rm{j}개 접시를 꺼낼 때의 최대치를 dp[i][j]로 계산하면 dp[N][P]가 제N개 창고에서 P개 접시를 꺼낼 때의 최대치를 요구하고자 하는 해답입니다.동적 계획법을 사용해 중도의 최대치를 계산하고 업데이트하면 조합 계산보다 대폭 계산 횟수가 줄어든다.
dp[i][j]시 최대치, 0\leq\rm{x}\leq\rm{min(j,K)}의 각 x에 대한 제i개 창고의 x개 분량의 합계와 제i-1개 창고에서 j-x 개량의 최대치와 업데이트(제i개 창고에서 x개, 다른 창고에서 j-x개를 꺼낼 때의 최대치의 합계, 최대치의 합계).

이루어지다

실현은 다음과 같다.dp[i][j]를 업데이트할 때 누적과 를 사용했지만cum sumsum의 배열 사이즈는 (N) 이고 dp의 배열 사이즈는 (N+1, P+1) 이며 dp[i]에 대응하는cumsum[i-1]이 됩니다.계산량은 O(N*K*P)입니다.

def cumulative_sum(stack, N, K):
    cum_sum = []
    for i in range(N):
        cum_sum_i = [0 for _ in range(K + 1)]
        for j in range(K):
            cum_sum_i[j + 1] = cum_sum_i[j] + stack[i][j]
        cum_sum.append(cum_sum_i)
    return cum_sum
    
def plates(stack, N, P, K):
    dp = [[0] * (P + 1) for _ in range(N + 1)]
    cum_sum = cumulative_sum(stack, N, K)
    for i in range(1, N + 1):
        for j in range(0, P + 1):
            dp[i][j] = 0
            for x in range(min(j, K) + 1):
                dp[i][j] = max(dp[i][j], cum_sum[i - 1][x] + dp[i - 1][j - x])
    return dp[N][P]

T = int(input())
for t in range(1, T + 1):
    N, K, P = list(map(int, input().split()))
    stack = []
    for _ in range(N):
        stack.append(list(map(int, input().split())))
    print('Case #{}: {}'.format(t, plates(stack, N, P, K)))