试题 算法提高 Trade on Verweggistan
资源限制
时间限制：1.0s 内存限制：128.0MB
问题描述
自从Peter Stuyvesant和Abel Tasman的日子以后，荷兰商人已经周游世界来买卖商品。有一次在Verweggistan的贸易，但是它在很短的时间后就结束了。在读完这个故事之后你就明白了。
在当时Verweggistan是非常受欢迎的，因为世界上只有那个地方的人知道怎样制作一个“prul”（或者“prullen”，荷兰语中的复数形式），并且如今只有很少的人知道什么是一个“prul”。
“prul”是在工场里生产的。当一个“prul”做完的时候，它被包装在一个箱子里，然后放在之前生产的“prul”所装的箱子堆的上面。
价格取决于生产“prul”所需要的时间。如果一切顺利，一个“prul”的价格会是1或者2弗罗林，但是在一个恶劣的日子，价格会很容易地上升到15弗罗林或者更高。“prul”在品质上没有什么差别，所有的“prul”具有相同的价值。
在这些天，“prul”在荷兰的售价为每件10弗罗林。交通运输的费用是可以忽略的，因为“prul”无论如何都会作为额外的东西被装载到要航行的船上。当一个荷兰商人去Verweggistan时，他有一个明确的目的：买“prul”，在荷兰销售，并且最大化他的利润。不幸的是，Verweggistan地区对“prul”的交易方式使得这比某些人预想的更为复杂。
有人认为这很简单，商人会买那些最便宜的“prul”，而那些售价比10弗罗林高的“prul”会一直不能出售。不幸的是，Verweggistan的所有工场按照一种奇怪的顺序销售“prul”。堆顶的箱子里的“prul”会最先销售，然后销售从顶上开始数的第二个箱子里的“prul”，以此类推。所以即使第五个箱子里的“prul”是最便宜的，商人也必须买它上面四个箱子里的“prul”才能得到它。
正如你想象的那样，这使得商人通过购买正确的“prul”的组合来最大化他们的利润是相当难的。没有电脑帮助他们的优化，他们迅速彻底失去了交易“prul”的兴趣。
在这个问题中，给你对几个工场里箱子堆的描述。你必须根据上面所给的限制，计算出一个商人通过购买箱子堆中的“prul”可以获得的最大利润。另外，你必须确定他需要买多少个“prul”才能获得最大利润。
输入格式
输入文件包含多组测试数据。每个测试数据的第一行是一个整数w(1<=w<=50)，该测试数据中工场的数目。
接下来有w行，每行描述一个放“prul”的箱子堆。每行的第一个整数b(0<=b<=20)，表示堆中的箱子数。接下来是b个正整数，表示堆中“prul”的价格（单位为弗罗林）。输入中箱子的顺序是从顶到底。
输入数据终止于w=0，不再有后续的描述内容。
输出格式
对于每组测试数据，输出测试点的编号(1,2…)。然后输出两行，第一行输出商人可以获得的最大利润。第二行输出为获得最大利润商人需要买的“prul”数量。如果这个数量不是唯一确定的，按照升序输出可能的值。如果有超过10种可能的取值，只输出10个最小的取值。
样例输入
1
6 12 3 10 7 16 5
2
5 7 3 11 9 10
9 1 2 3 4 10 16 10 4 16
0
样例输出
Workyards 1
Maximum profit is 8.
Number of pruls to buy: 4
Workyards 2
Maximum profit is 40.
Number of pruls to buy: 6 7 8 9 10 12 13
数据规模和约定
1<=w<=50，0<=b<=20，输入文件保证测试点个数不超过10。
- 用dp[i][j]记录买到第i个工厂第j个prul的利润情况
- 如果一个工厂购买的利润为负，则不购买，购买的数量为0
- 如果一个工厂在利润都最大的情况下有多种买法，则应该都记录
- 存储每一个工厂的可能购买数量以后，dfs求解最终总的购买数量
- 利用set自动排序的特点，存储总的购买数量，然后输出前十个
AC代码如下
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;const int MAXW = 51;
const int MAXB = 21;
int dp[MAXW][MAXB];
int line[MAXB];
vector<int> choice[MAXW]; //记录各个工厂选择的数量
set<int> ans; //可能购买的prul数量
set<int>::iterator IT;
int n; //测试组数void dfs(int i, int total) {
//递归求解购买的prul数量if (i == n) {
//当n个工厂都遍历过时，记录数量ans.insert(total);return;}for (int j = 0; j < choice[i].size(); j++)dfs(i + 1, total + choice[i][j]);
}int main() {
int ccase = 0; //第几组测试数据while (scanf("%d", &n) && n) {
ccase++;int total = 0; //总利润ans.clear();memset(dp, 0, sizeof(dp));memset(line, 0, sizeof(line));for (int i = 0; i < MAXW; i++)choice[i].clear(); //初始化变量for (int i = 0; i < n; i++) {
//每一组数据有几个工厂int num;int max_profit = -100;scanf("%d", &num);for (int j = 1; j <= num; j++) {
//每一个工厂scanf("%d", &line[j]);dp[i][j] = 10 - line[j] + dp[i][j - 1];max_profit = max(max_profit, dp[i][j]);}if (max_profit < 0) {
//一个都不买choice[i].push_back(0);}else if (max_profit == 0) {
//可以不购买，也可以买for (int j = 1; j <= num; j++)if (dp[i][j] == max_profit) //买到第几个prulchoice[i].push_back(j);choice[i].push_back(0);}else {
total += max_profit; //总利润增加for (int j = 1; j <= num; j++)if (dp[i][j] == max_profit)choice[i].push_back(j);}}dfs(0, 0); //求解购买prul的数量printf("Workyards %d\n", ccase);printf("Maximum profit is %d.\n", total);printf("Number of pruls to buy: ");int k = 0;for (IT = ans.begin(); (IT != ans.end() && k < 10); IT++) {
printf("%d ", *IT); //只要排前面十个的数量k++;}printf("\n");}return 0;
}