问题解决策略动态规划训练3
ai写的。
问题 A: 求子数组的最大和（动态规划）
题目描述
输入一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。
输入
一个整型数组。
输出
子数组的和的最大值。
输入输出样例
样例输入 #1
复制
1 -2 3 10 -4 7 2 -5样例输出 #1
复制
18提示
数组长度最大为 500005000050000
问题 B: 动态规划进阶题目之货币面值
题目描述
小虎是游戏中的一个国王，在他管理的国家中发行了很多不同面额的纸币，用这些纸币进行任意的组合可以在游戏中购买各种装备来提升自己。有一天，他突然很想知道这些纸币的组合不能表示的最小面额是多少，请聪明的你来帮助小虎来解决这个财政问题吧。
输入
输入包含多个测试用例，每组测试用例的第一行输入一个整数 NNN (N≤100)(N \le 100)(N≤100) 表示流通的纸币面额数量，第二行是 NNN 个纸币的具体表示面额，取值 [1,100][1, 100][1,100]。
输出
对于每组测试用例，输出一个整数，表示已经发行的所有纸币都不能表示的最小面额（已经发行的每个纸币面额最多只能使用一次,但面值可能有重复）。
输入输出样例
样例输入 #1
复制
5 1 2 3 9 100 5 1 2 4 9 100 5 1 2 4 7 100样例输出 #1
复制
7 8 15提示
注意一下给出的货币面值可能不是升序排列的。
#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { int n; while(cin >> n) { vector<int> a(n); int sum = 0; for(int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } sort(a.begin(), a.end()); vector<int> dp(sum + 1, 0); dp[0] = 1; for(int i = 0; i < n; i++) for(int j = sum; j >= a[i]; j--) if(dp[j - a[i]]) dp[j] = 1; int ans = 1; while(ans <= sum && dp[ans]) ans++; cout << ans << endl; } return 0; }问题 C: 动态规划进阶题目之最佳加法表达式
题目描述
有一个由 [1,9][1, 9][1,9] 组成的数字串，问如果将 mmm 个加号插入到这个数字串中，在各种可能形成的表达式中，值最小的那个表达式的值是多少。
例如，在 123412341234 中摆放 111 个加号，最好的摆法就是 12+3412+3412+34，和为 363636。
输入
有不超过 151515 组数据。
每组数据两行。
第一行是整数 mmm，表示有 mmm 个加号要放 (0≤m≤17)(0 \le m \le 17)(0≤m≤17)。
第二行是若干个数字。数字总数 nnn 不超过 181818 且 m≤n−1m \le n-1m≤n−1。
输出
对每组数据，输出最小加法表达式的值。
输入输出样例
样例输入 #1
复制
2 123456 1 123456 4 12345样例输出 #1
复制
102 579 15#include<iostream> #include<vector> #include<string> #include<algorithm> #include<climits> #define int long long using namespace std; signed main() { int m; string s; while(cin >> m >> s) { int n = s.size(); vector<vector<int>> num(n, vector<int>(n, 0)); for(int i = 0; i < n; i++) { int cur = 0; for(int j = i; j < n; j++) { cur = cur * 10 + (s[j] - '0'); num[i][j] = cur; } } vector<vector<int>> dp(n, vector<int>(m + 1, LLONG_MAX)); for(int i = 0; i < n; i++) dp[i][0] = num[0][i]; for(int j = 1; j <= m; j++) for(int i = j; i < n; i++) for(int k = j - 1; k < i; k++) if(dp[k][j-1] != LLONG_MAX) dp[i][j] = min(dp[i][j], dp[k][j-1] + num[k+1][i]); cout << dp[n-1][m] << endl; } return 0; }问题 D: 小A点菜
题目描述
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
不过 uim 由于买了一些书，口袋里只剩 MMM 元 (M≤10000)(M \le 10000)(M≤10000)。
餐馆虽低端，但是菜品种类不少，有 NNN 种 (N≤100)(N \le 100)(N≤100)，第 iii 种卖 aia_iai 元 (ai≤1000)(a_i \le 1000)(ai≤1000)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 111 秒。
输入
第一行是两个数字，表示 NNN 和 MMM。
第二行起 NNN 个正数 aia_iai（可以有相同的数字，每个数字均在 100010001000 以内）。
输出
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
输入输出样例
样例输入 #1
复制
4 4 1 1 2 2样例输出 #1
复制
3#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { int n, m; cin >> n >> m; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; vector<int> dp(m + 1, 0); dp[0] = 1; for(int i = 0; i < n; i++) for(int j = m; j >= a[i]; j--) dp[j] += dp[j - a[i]]; cout << dp[m]; return 0; }问题 E: 动态规划进阶题目之大盗阿福
题目描述
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 NNN 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入
输入的第一行是一个整数 TTT (T≤50)(T \le 50)(T≤50)，表示一共有 TTT 组数据。
接下来的每组数据，第一行是一个整数 NNN (1≤N≤100000)(1 \le N \le 100000)(1≤N≤100000)，表示一共有 NNN 家店铺。第二行是 NNN 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 100010001000 。
输出
对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
输入输出样例
样例输入 #1
复制
2 3 1 8 2 4 10 7 6 14样例输出 #1
复制
8 24提示
对于第一组样例，阿福选择第 222 家店铺行窃，获得的现金数量为 888。
对于第二组样例，阿福选择第 111 和 444 家店铺行窃，获得的现金数量为 10+14=2410 + 14 = 2410+14=24。
#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { int T; cin >> T; while(T--) { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; if(n == 1) { cout << a[0] << endl; continue; } vector<int> dp(n, 0); dp[0] = a[0]; dp[1] = max(a[0], a[1]); for(int i = 2; i < n; i++) dp[i] = max(dp[i-1], dp[i-2] + a[i]); cout << dp[n-1] << endl; } return 0; }