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−N+12-N+12−N+1 行：两个整数，每个“种类”题目的分数和耗时。
输出
一行，在给定的限制里可能得到的最大的分数。
输入输出样例
样例输入 #1
复制
300 4 100 60 250 120 120 100 35 20样例输出 #1
复制
605#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { int m, n; cin >> m >> n; vector<int> 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#include<iostream> #include<vector> #include<algorithm> #include<cstring> #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]; } int half = sum / 2; vector<int> 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#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { int n; cin >> n; vector<int> a(n); int sum = 0; for(int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } vector<vector<int>> dp(n, vector<int>(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[i+1][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 表示成一系列正整数之和，n=n1+n2+⋯+nkn = n_1 + n_2 + \dots + n_kn=n1+n2+⋯+nk，其中 n1≥n2≥⋯≥nk≥1n_1 \ge n_2 \ge \dots \ge n_k \ge 1n1≥n2≥⋯≥nk≥1，k≥1k \ge 1k≥1，正整数 nnn 的这种表示称为正整数 nnn 的划分，正整数 nnn 的不同的划分个数称为正整数 nnn 的划分数。
输入
标准的输入包含若干组测试数据，每组测试数据是一个整数 NNN (0<N≤50)(0 \lt N \le 50)(0<N≤50)。
输出
对于每组测试数据，输出 NNN 的划分数。
输入输出样例
样例输入 #1
复制
5样例输出 #1
复制
7#include<iostream> #include<vector> #include<algorithm> #define int long long using namespace std; signed main() { int n; while(cin >> n) { vector<vector<int>> dp(n + 1, vector<int>(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行是正整数n，1≤n≤100，表示有n堆石子。第二行有 n个数，分别表示每堆石子的个数。
输出
输出数据有两行，第1行中的数是最小得分，第2行中的数是最大得分。
输入输出样例
样例输入 #1
4 4 4 5 9样例输出 #1
43 54#include<iostream> #include<vector> #include<algorithm> #include<climits> #define int long long using namespace std; signed main() { int n; cin >> n; vector<int> a(2 * n); for(int i = 0; i < n; i++) { cin >> a[i]; a[i + n] = a[i]; } vector<int> s(2 * n + 1, 0); for(int i = 1; i <= 2 * n; i++) s[i] = s[i-1] + a[i-1]; vector<vector<int>> dpmax(2 * n, vector<int>(2 * n, 0)); vector<vector<int>> dpmin(2 * n, vector<int>(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[k+1][j] + s[j+1] - s[i]); dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k+1][j] + s[j+1] - s[i]); } } int ansmin = INT_MAX, ansmax = 0; for(int i = 0; i < n; i++) { ansmin = min(ansmin, dpmin[i][i+n-1]); ansmax = max(ansmax, dpmax[i][i+n-1]); } cout << ansmin << endl << ansmax; return 0; }
