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提示注意一下给出的货币面值可能不是升序排列的。#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int n; while(cin n) { vectorint a(n); int sum 0; for(int i 0; i n; i) { cin a[i]; sum a[i]; } sort(a.begin(), a.end()); vectorint 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 个加号最好的摆法就是 123412341234和为 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#includeiostream #includevector #includestring #includealgorithm #includeclimits #define int long long using namespace std; signed main() { int m; string s; while(cin m s) { int n s.size(); vectorvectorint num(n, vectorint(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; } } vectorvectorint dp(n, vectorint(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[k1][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#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int n, m; cin n m; vectorint a(n); for(int i 0; i n; i) cin a[i]; vectorint 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 家店铺行窃获得的现金数量为 10142410 14 24101424。#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int T; cin T; while(T--) { int n; cin n; vectorint a(n); for(int i 0; i n; i) cin a[i]; if(n 1) { cout a[0] endl; continue; } vectorint 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; }