阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。
阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。
他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
输入格式
输入的第一行是一个整数 T,表示一共有 T 组数据。
接下来的每组数据,第一行是一个整数 N ,表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过 1000。
输出格式
对于每组数据,输出一行。
该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
输入样例:
输出样例:
样例解释
对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8。
对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10+14=24。
解法一 这题 lc 上写过,还是比较简单,不过不是状态机的做法, 代表的是偷前 个房子的最大收益,然后直接线性 dp
T = int (input ()) while T > 0 : n = int (input ()) nums = list (map (int , input ().split())) f = [0 ] * (n+1 ) for i in range (1 , n+1 ): f[i] = max (f[i-1 ], (f[i-2 ] + nums[i-1 ]) if i-2 >= 0 else nums[i-1 ]) print (f[i]) T -= 1
用状态机来理解,每个房子有两种状态,「偷」或则「不偷」
偷,那么就得保证前一个房子「不偷」
不偷,那么就可以从前一个房子「偷或者不偷」状态转移过来,不影响当前状态
定义状态为 ,偷前 个房子,且第 个房子状态为 (0 不偷,1 偷)
T = int (input ()) while T > 0 : n = int (input ()) nums = list (map (int , input ().split())) f = [[0 for _ in range (2 )] for _ in range (n+1 )] for i in range (1 , n+1 ): f[i][0 ] = max (f[i-1 ][1 ], f[i-1 ][0 ]) f[i][1 ] = f[i-1 ][0 ] + nums[i-1 ] print (max (f[n][1 ], f[n][0 ])) T -= 1
比较 trick 的空间优化写法
T = int (input ()) while T > 0 : n = int (input ()) nums = list (map (int , input ().split())) f = [0 ] * 2 for i in range (1 , n+1 ): f[0 ], f[1 ] = max (f[1 ], f[0 ]), f[0 ] + nums[i-1 ] print (max (f[1 ], f[0 ])) T -= 1
给定一个长度为 的数组,数组中的第 个数字表示一个给定股票在第 天的价格。
设计一个算法来计算你所能获取的最大利润,你最多可以完成 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。一次买入卖出合为一笔交易。
输入格式
第一行包含整数 和 ,表示数组的长度以及你可以完成的最大交易数量。
第二行包含 个不超过 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
输入样例 1:
输出样例 1:
输入样例 2:
输出样例 2:
样例解释
样例 1:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
样例 2:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出,这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.
解法一 也是 lc 上的题,但是这里重写的时候没写出来。重新捋了思路,比之前的要更加清晰,希望下次可以直接写出来。
从状态机的角度考虑,有两个状态:「持仓」和「空仓」。围绕这两个状态进行转换。
从「持仓」到「空仓」的转换,说明卖掉了昨天手中持有的股票,并且完成了一次完整交易。或者今天按兵不动,维持前一天的状态
从「空仓」到「持仓」的转换,说明今天又购入了新的股票,开始了一轮新的交易 。或者今天按兵不动,维持前一天的状态
定义状态为: ,代表购买前 天的股票,进行了恰好 次交易,最终状态为 (0 空仓,1 持仓)
入口: ,不交易就不会持有股票,收益为 0, 其他状态收益为 ,避免非法转移
状态转移:
出口:
代码实现如下:
import java.util.*;import java.io.*;class Main { static int INF = -0x3f3f3f3f ; public static void main (String ...args) throws Exception { BufferedReader br = new BufferedReader (new InputStreamReader (System.in)); PrintWriter out = new PrintWriter (new BufferedOutputStream (System.out)); int [] in = read(br); int N = in[0 ], K = in[1 ]; int [] price = read(br); if (K > N/2 ) { out.println(maxProfit(price)); out.flush(); return ; } int [][][] dp = new int [N+1 ][K+1 ][2 ]; for (int i = 0 ; i <= N; i++) { for (int j = 0 ; j <= K; j++) { Arrays.fill(dp[i][j], INF); } dp[i][0 ][0 ] = 0 ; } int res = 0 ; for (int i = 1 ; i <= N; i++) { for (int j = 1 ; j <= K; j++) { dp[i][j][0 ] = Math.max(dp[i-1 ][j][1 ] + price[i-1 ], dp[i-1 ][j][0 ]); dp[i][j][1 ] = Math.max(dp[i-1 ][j-1 ][0 ] - price[i-1 ], dp[i-1 ][j][1 ]); res = Math.max(dp[i][j][0 ], res); } } out.println(res); out.flush(); } public static int maxProfit (int [] price) { int N = price.length; int [][] dp = new int [N+1 ][2 ]; for (int i = 0 ; i <= N; i++) { Arrays.fill(dp[i], INF); } dp[0 ][0 ] = 0 ; int res = 0 ; for (int i = 1 ; i <= N; i++) { dp[i][0 ] = Math.max(dp[i-1 ][1 ] + price[i-1 ], dp[i-1 ][0 ]); dp[i][1 ] = Math.max(dp[i-1 ][0 ] - price[i-1 ], dp[i-1 ][1 ]); res = Math.max(dp[i][0 ], res); } return res; } public static int [] read(BufferedReader br) throws Exception{ return Arrays.stream(br.readLine().split(" " )).mapToInt(Integer::parseInt).toArray(); } }
这里就不写降维的了,降维会隐藏一些信息。最好是先写出原始的,如果 MLE 了,再考虑降维。直接写降维的可能会不知道怎么对的,也不知道怎么错的(太菜了)。
给定一个长度为 的数组,数组中的第 个数字表示一个给定股票在第 天的价格,再给定一个非负整数 ,表示交易股票的手续费用。
设计一个算法来计算你所能获取的最大利润。
你可以无限次地完成交易,但是你每次交易都需要支付手续费。
注意 : 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
输入格式
第一行包含两个整数 N 和 f,分别表示数组的长度以及每笔交易的手续费用。
第二行包含 N 个不超过 10000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
输入样例:
输出样例:
样例解释
在第 1 天(股票价格 = 1)的时候买入,在第 4 天(股票价格 = 8)的时候卖出,这笔交易所能获得利润 = 8-1-2 = 5 。随后,在第 5 天(股票价格 = 4)的时候买入,在第 6 天 (股票价格 = 9)的时候卖出,这笔交易所能获得利润 = 9-4-2 = 3 。共得利润 5+3 = 8。
解法一 package mainimport ( "bufio" "fmt" "os" "strconv" "strings" ) var reader = bufio.NewReader(os.Stdin)func main () { INF := int (-0x3f3f3f3f ) reader := bufio.NewReader(os.Stdin) in := ReadArray(reader) N, F := in[0 ], in[1 ] price := ReadArray(reader) dp := make ([][]int , N+1 ) for i := 0 ; i <= N; i++ { dp[i] = make ([]int , 2 ) dp[i][0 ] = INF dp[i][1 ] = INF } dp[0 ][0 ] = 0 res := 0 for i := 1 ; i <= N; i++ { dp[i][0 ] = Max(dp[i-1 ][1 ]+price[i-1 ]-F, dp[i-1 ][0 ]) dp[i][1 ] = Max(dp[i-1 ][0 ]-price[i-1 ], dp[i-1 ][1 ]) res = Max(res, dp[i][0 ]) } fmt.Println(res) } func Max (a, b int ) int { if a > b { return a } return b } func ReadLine (reader *bufio.Reader) string { line, _ := reader.ReadString('\n' ) return strings.TrimRight(line, "\n" ) } func ReadInt (reader *bufio.Reader) int { num, _ := strconv.Atoi(ReadLine(reader)) return num } func ReadArray (reader *bufio.Reader) []int { line := ReadLine(reader) strs := strings.Split(line, " " ) nums := make ([]int , len (strs)) for i, s := range strs { nums[i], _ = strconv.Atoi(s) } return nums }
给定一个长度为 的数组,数组中的第 个数字表示一个给定股票在第 天的价格。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
输入格式
第一行包含整数 ,表示数组长度。
第二行包含 个不超过 10000 的正整数,表示完整的数组。
输出格式
输出一个整数,表示最大利润。
数据范围
输入样例:
输出样例:
样例解释
对应的交易状态为:[买入,卖出,冷冻期,买入,卖出],第一笔交易可得利润 2-1 = 1,第二笔交易可得利润 2-0 = 2,共得利润 1+2 = 3。
解法一 个人觉得这题直接线性 DP 就好了,状态机的反而不容易理解。设置 为考虑前 天的股票,第 天的状态为 (0 为空仓,1 为持仓)
package mainimport ( "bufio" "fmt" "os" "strconv" "strings" ) var reader = bufio.NewReader(os.Stdin)func main () { n := ReadInt(reader) price := ReadArray(reader) dp := make ([][2 ]int , n+1 ) dp[0 ][1 ] = -price[0 ] var res = 0 for i := 1 ; i <= n; i++ { dp[i][0 ] = Max(dp[i-1 ][1 ]+price[i-1 ], dp[i-1 ][0 ]) if i-2 >= 0 { dp[i][1 ] = Max(dp[i-2 ][0 ]-price[i-1 ], dp[i-1 ][1 ]) } else { dp[i][1 ] = Max(-price[i-1 ], dp[i-1 ][1 ]) } res = Max(res, dp[i][0 ]) } fmt.Println(res) } func Max (a, b int ) int { if a > b { return a } return b } func ReadLine (reader *bufio.Reader) string { line, _ := reader.ReadString('\n' ) return strings.TrimRight(line, "\n" ) } func ReadInt (reader *bufio.Reader) int { num, _ := strconv.Atoi(ReadLine(reader)) return num } func ReadArray (reader *bufio.Reader) []int { line := ReadLine(reader) strs := strings.Split(line, " " ) nums := make ([]int , len (strs)) for i, s := range strs { nums[i], _ = strconv.Atoi(s) } return nums }
你现在需要设计一个密码 , 需要满足:
的长度是 ;
只包含小写英文字母;
不包含子串 ;
例如:abc 和 abcde 是 abcde 的子串,abd 不是 abcde 的子串。
请问共有多少种不同的密码满足要求?
由于答案会非常大,请输出答案模 的余数。
输入格式
第一行输入整数 ,表示密码的长度。
第二行输入字符串 , 中只包含小写字母。
输出格式
输出一个正整数,表示总方案数模 后的结果。
数据范围
输入样例 1:
输出样例 1:
输入样例 2:
输出样例 2:
解法一 这里实际上是一个比较复杂的状态机,还结合了kmp,属实是有点难了,我也看了好久。这里建议先熟悉下kmp,这里我也更新了我之前的kmp的写法。
package mainimport ( "bufio" "fmt" "os" "strconv" "strings" ) var MOD = int (1e9 + 7 )func main () { f, _ := os.Open("../input.txt" ) reader := bufio.NewReader(f) n := ReadInt(reader) t := ReadLine(reader) m := len (t) dp := make (map [int ]map [int ]int ) for i := 0 ; i <= n; i++ { dp[i] = make (map [int ]int ) } next := make ([]int , m) next[0 ] = -1 for i, j := -1 , 1 ; j < m; j++ { for i > -1 && t[i+1 ] != t[j] { i = next[i] } if t[i+1 ] == t[j] { i++ } next[j] = i } dp[0 ][-1 ] = 1 for i := 0 ; i < n; i++ { for c := 'a' ; c <= 'z' ; c++ { for j := -1 ; j < m-1 ; j++ { u := j for u > -1 && byte (c) != t[u+1 ] { u = next[u] } if byte (c) == t[u+1 ] { u++ } if u < m-1 { dp[i+1 ][u] = (dp[i+1 ][u] + dp[i][j]) % MOD } } } } var res = 0 for i := -1 ; i < m-1 ; i++ { res = (res + dp[n][i]) % MOD } fmt.Println(res) } func ReadLine (reader *bufio.Reader) string { line, _ := reader.ReadString('\n' ) return strings.TrimRight(line, "\n" ) } func ReadInt (reader *bufio.Reader) int { num, _ := strconv.Atoi(ReadLine(reader)) return num }