ai写的。问题 A: 3.1.2 Score Inflation 总分题目描述学生在我们 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分这需要你的帮助。我们可以从几个种类中选取竞赛的题目这里的一个“种类”是指一个竞赛题目的集合解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉 USACO 的职员应该从每一个种类中选取多少题目使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间 MMM (1≤M≤10000)(1 \le M \le 10000)(1≤M≤10000)不要担心你要到了训练营中才会有长时间的比赛和“种类”的数目 NNN (1≤N≤10000)(1 \le N \le 10000)(1≤N≤10000)。后面的每一行将包括两个整数来描述一个“种类”第一个整数是解决这种题目能得的分数 (1≤points≤10000)(1 \le points \le 10000)(1≤points≤10000)第二个整数是解决这种题目所需的时间 (1≤minutes≤10000)(1 \le minutes \le 10000)(1≤minutes≤10000)。你的程序应该确定我们应该从每个“种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。输入第 111 行M,NM, NM,N竞赛的时间和题目种类的数目。第 2−N12-N12−N1 行两个整数每个“种类”题目的分数和耗时。输出一行在给定的限制里可能得到的最大的分数。输入输出样例样例输入 #1复制300 4 100 60 250 120 120 100 35 20样例输出 #1复制605#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int m, n; cin m n; vectorint dp(m 1, 0); for(int i 0; i n; i) { int p, t; cin p t; for(int j t; j m; j) dp[j] max(dp[j], dp[j - t] p); } cout dp[m]; return 0; }问题 B: 愚公的遗愿题目描述愚公留下遗愿让他的两个儿子愚大和愚二完成他移山的愿望将石头搬出大山。一直以来愚大背大石头将小石头留给弟弟愚二背。愚二长大后想分担哥哥的负担要求背大石头让哥哥背小石头。愚大不同意。兄弟二人多次讨论也不能提出一个公平背石头的方案。假设有 nnn 块石头将这 nnn 个石头尽可能平分给兄弟二人即两人分得的石头重量差异最小。请你帮助愚家兄弟解决这个问题。输入多组输入对于每组数据第一行一个整数 nnn (3≤n≤1000)(3 \le n \le 1000)(3≤n≤1000)表示石头的数目第二行nnn 个整数对于每个整数 aia_iai (1≤ai≤50)(1 \le a_i \le 50)(1≤ai≤50)表示第 iii 块石头的重量。输出对于每组输入输出两个数 x,yx, yx,y (x≤y)(x \le y)(x≤y)分别表示两个兄弟背的石头总重量。输入输出样例样例输入 #1复制3 1 2 3样例输出 #1复制3 3#includeiostream #includevector #includealgorithm #includecstring #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]; } int half sum / 2; vectorint dp(half 1, 0); for(int i 0; i n; i) for(int j half; j a[i]; j--) dp[j] max(dp[j], dp[j - a[i]] a[i]); int x dp[half]; int y sum - x; if(x y) swap(x, y); cout x y endl; } return 0; }问题 C: 3.3.5 A Game 游戏题目描述有如下一个双人游戏NNN (2≤N≤100)(2 \le N \le 100)(2≤N≤100) 个正整数的序列放在一个游戏平台上两人轮流从序列的两端取数取数后该数字被去掉并累加到本玩家的得分中当数取尽时游戏结束以最终得分多者为胜。编一个执行最优策略的程序最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。输入第一行正整数N, 表示序列中正整数的个数。第二行至末尾用空格分隔的N个正整数大小为 1−2001-2001−200。输出只有一行用空格分隔的两个整数依次为玩家一和玩家二最终的得分。输入输出样例样例输入 #1复制6 4 7 2 9 5 2样例输出 #1复制18 11#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int n; cin n; vectorint a(n); int sum 0; for(int i 0; i n; i) { cin a[i]; sum a[i]; } vectorvectorint dp(n, vectorint(n, 0)); for(int i 0; i n; i) dp[i][i] a[i]; for(int len 2; len n; len) for(int i 0; i len - 1 n; i) { int j i len - 1; dp[i][j] max(a[i] - dp[i1][j], a[j] - dp[i][j-1]); } int diff dp[0][n-1]; int x (sum diff) / 2; int y (sum - diff) / 2; cout x y; return 0; }问题 D: 简单的整数划分问题题目描述将正整数 nnn 表示成一系列正整数之和nn1n2⋯nkn n_1 n_2 \dots n_knn1n2⋯nk其中 n1≥n2≥⋯≥nk≥1n_1 \ge n_2 \ge \dots \ge n_k \ge 1n1≥n2≥⋯≥nk≥1k≥1k \ge 1k≥1正整数 nnn 的这种表示称为正整数 nnn 的划分正整数 nnn 的不同的划分个数称为正整数 nnn 的划分数。输入标准的输入包含若干组测试数据每组测试数据是一个整数 NNN (0N≤50)(0 \lt N \le 50)(0N≤50)。输出对于每组测试数据输出 NNN 的划分数。输入输出样例样例输入 #1复制5样例输出 #1复制7#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int n; while(cin n) { vectorvectorint dp(n 1, vectorint(n 1, 0)); for(int i 0; i n; i) dp[0][i] 1; for(int i 1; i n; i) for(int j 1; j n; j) { if(j i) dp[i][j] dp[i][j-1] dp[i-j][j]; else dp[i][j] dp[i][i]; } cout dp[n][n] endl; } return 0; }问题 E: 石子合并问题题目描述在一个圆形操场的四周摆放着n堆石子(石子首尾相接)。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆并将新的一堆石子数记为该次合并的得分。试设计一个算法计算出将n堆石子合并成一堆的最小得分和最大得分。 对于给定n堆石子,计算合并成一堆的最小得分和最大得分。输入输入数据的第1行是正整数n1≤n≤100表示有n堆石子。第二行有 n个数分别表示每堆石子的个数。输出输出数据有两行第1行中的数是最小得分第2行中的数是最大得分。输入输出样例样例输入 #14 4 4 5 9样例输出 #143 54#includeiostream #includevector #includealgorithm #includeclimits #define int long long using namespace std; signed main() { int n; cin n; vectorint a(2 * n); for(int i 0; i n; i) { cin a[i]; a[i n] a[i]; } vectorint s(2 * n 1, 0); for(int i 1; i 2 * n; i) s[i] s[i-1] a[i-1]; vectorvectorint dpmax(2 * n, vectorint(2 * n, 0)); vectorvectorint dpmin(2 * n, vectorint(2 * n, INT_MAX)); for(int i 0; i 2 * n; i) dpmin[i][i] 0; for(int len 2; len n; len) for(int i 0; i len - 1 2 * n; i) { int j i len - 1; for(int k i; k j; k) { dpmax[i][j] max(dpmax[i][j], dpmax[i][k] dpmax[k1][j] s[j1] - s[i]); dpmin[i][j] min(dpmin[i][j], dpmin[i][k] dpmin[k1][j] s[j1] - s[i]); } } int ansmin INT_MAX, ansmax 0; for(int i 0; i n; i) { ansmin min(ansmin, dpmin[i][in-1]); ansmax max(ansmax, dpmax[i][in-1]); } cout ansmin endl ansmax; return 0; }
问题解决策略动态规划训练2
ai写的。问题 A: 3.1.2 Score Inflation 总分题目描述学生在我们 USACO 的竞赛中的得分越多我们越高兴。我们试着设计我们的竞赛以便人们能尽可能的多得分这需要你的帮助。我们可以从几个种类中选取竞赛的题目这里的一个“种类”是指一个竞赛题目的集合解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉 USACO 的职员应该从每一个种类中选取多少题目使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间 MMM (1≤M≤10000)(1 \le M \le 10000)(1≤M≤10000)不要担心你要到了训练营中才会有长时间的比赛和“种类”的数目 NNN (1≤N≤10000)(1 \le N \le 10000)(1≤N≤10000)。后面的每一行将包括两个整数来描述一个“种类”第一个整数是解决这种题目能得的分数 (1≤points≤10000)(1 \le points \le 10000)(1≤points≤10000)第二个整数是解决这种题目所需的时间 (1≤minutes≤10000)(1 \le minutes \le 10000)(1≤minutes≤10000)。你的程序应该确定我们应该从每个“种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。输入第 111 行M,NM, NM,N竞赛的时间和题目种类的数目。第 2−N12-N12−N1 行两个整数每个“种类”题目的分数和耗时。输出一行在给定的限制里可能得到的最大的分数。输入输出样例样例输入 #1复制300 4 100 60 250 120 120 100 35 20样例输出 #1复制605#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int m, n; cin m n; vectorint dp(m 1, 0); for(int i 0; i n; i) { int p, t; cin p t; for(int j t; j m; j) dp[j] max(dp[j], dp[j - t] p); } cout dp[m]; return 0; }问题 B: 愚公的遗愿题目描述愚公留下遗愿让他的两个儿子愚大和愚二完成他移山的愿望将石头搬出大山。一直以来愚大背大石头将小石头留给弟弟愚二背。愚二长大后想分担哥哥的负担要求背大石头让哥哥背小石头。愚大不同意。兄弟二人多次讨论也不能提出一个公平背石头的方案。假设有 nnn 块石头将这 nnn 个石头尽可能平分给兄弟二人即两人分得的石头重量差异最小。请你帮助愚家兄弟解决这个问题。输入多组输入对于每组数据第一行一个整数 nnn (3≤n≤1000)(3 \le n \le 1000)(3≤n≤1000)表示石头的数目第二行nnn 个整数对于每个整数 aia_iai (1≤ai≤50)(1 \le a_i \le 50)(1≤ai≤50)表示第 iii 块石头的重量。输出对于每组输入输出两个数 x,yx, yx,y (x≤y)(x \le y)(x≤y)分别表示两个兄弟背的石头总重量。输入输出样例样例输入 #1复制3 1 2 3样例输出 #1复制3 3#includeiostream #includevector #includealgorithm #includecstring #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]; } int half sum / 2; vectorint dp(half 1, 0); for(int i 0; i n; i) for(int j half; j a[i]; j--) dp[j] max(dp[j], dp[j - a[i]] a[i]); int x dp[half]; int y sum - x; if(x y) swap(x, y); cout x y endl; } return 0; }问题 C: 3.3.5 A Game 游戏题目描述有如下一个双人游戏NNN (2≤N≤100)(2 \le N \le 100)(2≤N≤100) 个正整数的序列放在一个游戏平台上两人轮流从序列的两端取数取数后该数字被去掉并累加到本玩家的得分中当数取尽时游戏结束以最终得分多者为胜。编一个执行最优策略的程序最优策略就是使自己能得到在当前情况下最大的可能的总分的策略。你的程序要始终为第二位玩家执行最优策略。输入第一行正整数N, 表示序列中正整数的个数。第二行至末尾用空格分隔的N个正整数大小为 1−2001-2001−200。输出只有一行用空格分隔的两个整数依次为玩家一和玩家二最终的得分。输入输出样例样例输入 #1复制6 4 7 2 9 5 2样例输出 #1复制18 11#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int n; cin n; vectorint a(n); int sum 0; for(int i 0; i n; i) { cin a[i]; sum a[i]; } vectorvectorint dp(n, vectorint(n, 0)); for(int i 0; i n; i) dp[i][i] a[i]; for(int len 2; len n; len) for(int i 0; i len - 1 n; i) { int j i len - 1; dp[i][j] max(a[i] - dp[i1][j], a[j] - dp[i][j-1]); } int diff dp[0][n-1]; int x (sum diff) / 2; int y (sum - diff) / 2; cout x y; return 0; }问题 D: 简单的整数划分问题题目描述将正整数 nnn 表示成一系列正整数之和nn1n2⋯nkn n_1 n_2 \dots n_knn1n2⋯nk其中 n1≥n2≥⋯≥nk≥1n_1 \ge n_2 \ge \dots \ge n_k \ge 1n1≥n2≥⋯≥nk≥1k≥1k \ge 1k≥1正整数 nnn 的这种表示称为正整数 nnn 的划分正整数 nnn 的不同的划分个数称为正整数 nnn 的划分数。输入标准的输入包含若干组测试数据每组测试数据是一个整数 NNN (0N≤50)(0 \lt N \le 50)(0N≤50)。输出对于每组测试数据输出 NNN 的划分数。输入输出样例样例输入 #1复制5样例输出 #1复制7#includeiostream #includevector #includealgorithm #define int long long using namespace std; signed main() { int n; while(cin n) { vectorvectorint dp(n 1, vectorint(n 1, 0)); for(int i 0; i n; i) dp[0][i] 1; for(int i 1; i n; i) for(int j 1; j n; j) { if(j i) dp[i][j] dp[i][j-1] dp[i-j][j]; else dp[i][j] dp[i][i]; } cout dp[n][n] endl; } return 0; }问题 E: 石子合并问题题目描述在一个圆形操场的四周摆放着n堆石子(石子首尾相接)。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆并将新的一堆石子数记为该次合并的得分。试设计一个算法计算出将n堆石子合并成一堆的最小得分和最大得分。 对于给定n堆石子,计算合并成一堆的最小得分和最大得分。输入输入数据的第1行是正整数n1≤n≤100表示有n堆石子。第二行有 n个数分别表示每堆石子的个数。输出输出数据有两行第1行中的数是最小得分第2行中的数是最大得分。输入输出样例样例输入 #14 4 4 5 9样例输出 #143 54#includeiostream #includevector #includealgorithm #includeclimits #define int long long using namespace std; signed main() { int n; cin n; vectorint a(2 * n); for(int i 0; i n; i) { cin a[i]; a[i n] a[i]; } vectorint s(2 * n 1, 0); for(int i 1; i 2 * n; i) s[i] s[i-1] a[i-1]; vectorvectorint dpmax(2 * n, vectorint(2 * n, 0)); vectorvectorint dpmin(2 * n, vectorint(2 * n, INT_MAX)); for(int i 0; i 2 * n; i) dpmin[i][i] 0; for(int len 2; len n; len) for(int i 0; i len - 1 2 * n; i) { int j i len - 1; for(int k i; k j; k) { dpmax[i][j] max(dpmax[i][j], dpmax[i][k] dpmax[k1][j] s[j1] - s[i]); dpmin[i][j] min(dpmin[i][j], dpmin[i][k] dpmin[k1][j] s[j1] - s[i]); } } int ansmin INT_MAX, ansmax 0; for(int i 0; i n; i) { ansmin min(ansmin, dpmin[i][in-1]); ansmax max(ansmax, dpmax[i][in-1]); } cout ansmin endl ansmax; return 0; }
