龙与地下城游戏问题

Go 解法, 执行用时: 42ms, 内存消耗: 8768KB, 提交时间: 2020-02-01

package main

import (
    "bufio"
    "fmt"
    "os"
)
/*-------------------INPUT-------------------*/
const N, Inf = 1005, 0x3f3f3f3f
var row, col int
var nums [N][N]int

func min(x, y int) int {
    if x < y { return x}
    return y
}
func max(x, y int) int {
    if x > y { return x}
    return y
}

var dp [N]int

func solve() int {
    dp[col] = 1
    for i := col - 1; i >= 0; i-- {
        dp[i] = max(1, dp[i+1] - nums[row-1][i])
    }
    dp[col] = Inf
    for i := row - 2; i >= 0; i-- {
        for j := col - 1; j >= 0; j-- {
            dp[j] = max(1, min(dp[j], dp[j+1]) - nums[i][j])
        }
    }
    return dp[0]
}

var in = bufio.NewReader(os.Stdin)
func read() (x int) {
    neg := false
    c, _ := in.ReadByte()
    for ; c < '0'; c, _ = in.ReadByte() {
        neg = '-' == c
    }
    for ; c >= '0'; c, _ = in.ReadByte() {
        x = x * 10 + int(c) & 15
    }
    if neg { x = -x}
    return
}

func main() {
    row = read()
    col = read()
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ { nums[i][j] = read()}
    }
    fmt.Println(solve())
}

Go 解法, 执行用时: 54ms, 内存消耗: 8808KB, 提交时间: 2022-05-08

package main

import (
	"bufio"
	"fmt"
	"os"
)

/*-------------------INPUT-------------------*/
const N, Inf = 1005, 0x3f3f3f3f

var row, col int
var nums [N][N]int

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

var dp [N]int

func solve() int {
	dp[col] = 1
	for i := col - 1; i >= 0; i-- {
		dp[i] = max(1, dp[i+1]-nums[row-1][i])
	}
	dp[col] = Inf
	for i := row - 2; i >= 0; i-- {
		for j := col - 1; j >= 0; j-- {
			dp[j] = max(1, min(dp[j], dp[j+1])-nums[i][j])
		}
	}
	return dp[0]
}

var in = bufio.NewReader(os.Stdin)

func read() (x int) {
	neg := false
	c, _ := in.ReadByte()
	for ; c < '0'; c, _ = in.ReadByte() {
		neg = '-' == c
	}
	for ; c >= '0'; c, _ = in.ReadByte() {
		x = x*10 + int(c)&15
	}
	if neg {
		x = -x
	}
	return
}

func main() {
	row = read()
	col = read()
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			nums[i][j] = read()
		}
	}
	fmt.Println(solve())
}

Go 解法, 执行用时: 57ms, 内存消耗: 15008KB, 提交时间: 2022-04-10

package main

import (
	"bufio"
	"fmt"
	"os"
)

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

var in = bufio.NewReader(os.Stdin)

func read() (x int) {
	neg := false
	c, _ := in.ReadByte()
	for ; c < '0'; c, _ = in.ReadByte() {
		neg = '-' == c
	}
	for ; c >= '0'; c, _ = in.ReadByte() {
		x = x*10 + int(c)&15
	}
	if neg {
		x = -x
	}
	return
}

func main() {
	var length, width int
	_, err := fmt.Scan(&length, &width)
	for err == nil {
		matrix := make([][]int, length)
		dp := make([]int, width)
		for y := 0; y < length; y++ {
			matrix[y] = make([]int, width)
			for x := 0; x < width; x++ {
				matrix[y][x] = read()
			}
		}

		dp[width-1] = max(1-matrix[length-1][width-1], 1)
		for x := width - 2; x >= 0; x-- {
			dp[x] = max(dp[x+1]-matrix[length-1][x], 1)
		}
		for y := length - 2; y >= 0; y-- {
			dp[width-1] = max(dp[width-1]-matrix[y][width-1], 1)
			for x := width - 2; x >= 0; x-- {
				dp[x] = max(min(dp[x+1], dp[x])-matrix[y][x], 1)
			}
		}

		// fmt.Println(dp)

		fmt.Println(dp[0])

		_, err = fmt.Scan(&length, &width)
	}
}

Go 解法, 执行用时: 60ms, 内存消耗: 21396KB, 提交时间: 2022-07-14

package main
 
import (
    "bufio"
    "fmt"
    "os"
)
 
/*
dp[i][j] 表示到达 matrix[i][j] 的最少血量
采用逆推，从右下角往左上角推
// 至少需要有 1 滴血, base case
dp[n-1][m-1] = myMax(1-matrix[n-1][m-1], 1)
 
最后一列
dp[i][m-1] = myMax(dp[i+1][m-1]-matrix[i][m-1], 1)
 
最后一行
dp[n-1][j] = myMax(dp[n-1][j+1]-matrix[n-1][j], 1)
 
dp[i][j] = myMax(myMin(dp[i+1][j], dp[i][j+1])-matrix[i][j], 1)
*/
func getResult(n, m int, matrix [1001][1001]int) int {
    // 至少需要有 1 滴血, base case
    dp[m-1] = myMax(1-matrix[n-1][m-1], 1)
 
    // 最后一行
    for j:=m-2;j>=0;j-- {
        dp[j] = myMax(dp[j+1]-matrix[n-1][j], 1)
    }
     
    for i:=n-2;i>=0;i-- {
        dp[m-1] = myMax(dp[m-1]-matrix[i][m-1], 1)
        for j:=m-2;j>=0;j-- {
            dp[j] = myMax(myMin(dp[j], dp[j+1])-matrix[i][j], 1)
        }
    }
 
    return dp[0]
}
 
func myMax(x, y int) int {
    if x > y {
        return x
    }
    return y
}
 
func myMin(x, y int) int {
    if x < y {
        return x
    }
    return y
}
 
 
var in = bufio.NewReader(os.Stdin)
 
func read() (x int) {
    c, _ := in.ReadByte()
    neg := false
    for ; c < '0';c, _ = in.ReadByte() {
        neg = c == '-'
    }
    for ; c >= '0';c, _ = in.ReadByte() {
        x = x*10 + int(c)&15
    }
    if neg {
        x = -x
    }
    return
}
 
var matrix [1001][1001]int
var dp [1001]int
 
func main() {
    n := read()
    m := read()
     
    for i:=0;i<n;i++ {
        for j:=0;j<m;j++ {
            matrix[i][j] = read()
        }
    }
    fmt.Printf("%d\n", getResult(n, m, matrix))
}

Go 解法, 执行用时: 66ms, 内存消耗: 16624KB, 提交时间: 2022-06-28

package main

import (
	"bufio"
	"fmt"
	"os"
)

/*
dp[i][j] 表示到达 matrix[i][j] 的最少血量
采用逆推，从右下角往左上角推
// 至少需要有 1 滴血, base case
dp[n-1][m-1] = myMax(1-matrix[n-1][m-1], 1)

最后一列
dp[i][m-1] = myMax(dp[i+1][m-1]-matrix[i][m-1], 1)

最后一行
dp[n-1][j] = myMax(dp[n-1][j+1]-matrix[n-1][j], 1)

dp[i][j] = myMax(myMin(dp[i+1][j], dp[i][j+1])-matrix[i][j], 1)
*/
func getResult(n, m int, matrix [1001][1001]int) int {
	// 至少需要有 1 滴血, base case
	dp[m-1] = myMax(1-matrix[n-1][m-1], 1)

    // 最后一行
	for j:=m-2;j>=0;j-- {
		dp[j] = myMax(dp[j+1]-matrix[n-1][j], 1)
	}
    
	for i:=n-2;i>=0;i-- {
        dp[m-1] = myMax(dp[m-1]-matrix[i][m-1], 1)
		for j:=m-2;j>=0;j-- {
			dp[j] = myMax(myMin(dp[j], dp[j+1])-matrix[i][j], 1)
		}
	}

	return dp[0]
}

func myMax(x, y int) int {
	if x > y {
		return x
	}
	return y
}

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


var in = bufio.NewReader(os.Stdin)

func read() (x int) {
	c, _ := in.ReadByte()
	neg := false
	for ; c < '0';c, _ = in.ReadByte() {
		neg = c == '-'
	}
	for ; c >= '0';c, _ = in.ReadByte() {
		x = x*10 + int(c)&15
	}
	if neg {
		x = -x
	}
	return
}

var matrix [1001][1001]int
var dp [1001]int

func main() {
	n := read()
	m := read()
	
	for i:=0;i<n;i++ {
		for j:=0;j<m;j++ {
			matrix[i][j] = read()
		}
	}
	fmt.Printf("%d\n", getResult(n, m, matrix))
}

详情