leetcode-go/oj/360-2018-spring/1-snatch-gold.go

// http://exercise.acmcoder.com/quesexcuse?paperId=213

package main

import "fmt"

func main() {
	var T int
	fmt.Scan(&T)
	for cid := 1; cid <= T; cid++ {
		var n int
		fmt.Scan(&n)
		gold := make([]int, n+1)
		for i := 1; i <= n; i++ {
			fmt.Scan(&gold[i])
			gold[i] += gold[i-1]
		}
		dp := make([][]int, n)
		for i := range dp {
			dp[i] = make([]int, n)
		}
		for i := n - 1; 0 <= i; i-- {
			for j := i; j < n; j++ {
				if i == j {
					dp[i][j] = gold[i+1] - gold[i]
					continue
				}
				dp[i][j] = gold[j+1] - gold[i] - minInt(dp[i+1][j], dp[i][j-1])
			}
		}
		fmt.Printf("Case #%d: %d %d\n", cid, dp[0][n-1], gold[n]-gold[0]-dp[0][n-1])
	}
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}