uva 812 Trade on Verweggistan

题意:

  给w个货架, 每个货架上有bi个货物, 每次只能拿最上面的货物, 每个货物有个价值, 所有货物的售价均为10。

  问:能获得的最大利润, 以及能获得这个利润需要多少个货物。 (有多种组合时只需输出前10种)

思路:

  最开始我是先将最大价值预处理了出来, 然后dfs查找方案数, 结果超时了, 后来发现复杂度是O(w*bi), 完全的暴力,可以先将每个货架的最大利润处理出来, 同时处理出来获得这个最大利润所需要的物品数。

  后来又WA了几发, 第一次是发现自己没有处理如果利润为负时, 结果应该输出0的情况。

  第二次发现没有处理某个货架最大利润为0时可以一个都不取的情况。

代码:

  

 #include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <fstream>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define eps 1e-6
#define MAXN 100
#define MAXM 30
#define dd {cout<<"debug"<<endl;}
#define pa {system("pause");}
#define p(x) {printf("%d\n", x);}
#define pd(x) {printf("%.7lf\n", x);}
#define k(x) {printf("Case %d: ", ++x);}
#define s(x) {scanf("%d", &x);}
#define sd(x) {scanf("%lf", &x);}
#define mes(x, d) {memset(x, d, sizeof(x));}
#define do(i, x) for(i = 0; i < x; i ++)
#define dod(i, x, l) for(i = x; i >= l; i --)
#define doe(i, x) for(i = 1; i <= x; i ++)
int w;
int f[MAXN][MAXM];
int max_ans, kcase = ;
set <int> ans;
vector <int> g[MAXN];
void read()
{
max_ans = ;
for(int i = ; i < w; i ++)
{
scanf("%d", &f[i][]); int sum = ;
int max_tmp = ;
g[i].clear();
for(int j = ; j <= f[i][]; j ++)
{
scanf("%d", &f[i][j]);
f[i][j] = - f[i][j];
sum += f[i][j];
if(sum > max_tmp)
{
max_tmp = sum;
g[i].clear();
}
if(sum == max_tmp)
g[i].push_back(j);
}
if(g[i].empty() || max_tmp == ) g[i].push_back(); //!!!
max_ans += max_tmp;
}
}
void dfs(int pos, int num)
{
if(pos == w)
{
ans.insert(num);
return ;
} for(int i = ; i < g[pos].size(); i ++)
dfs(pos + , num + g[pos][i]);
}
void show()
{
int cnt = ;
printf("Workyards %d\n", ++ kcase);
printf("Maximum profit is %d.\n", max_ans);
printf("Number of pruls to buy:");
for(set <int>::iterator it = ans.begin(); it != ans.end() && cnt < ; it ++, cnt ++)
printf(" %d", *it);
printf("\n");
}
void solve()
{
ans.clear();
dfs(, );
show();
} int main()
{
while(scanf("%d", &w) && w)
{
if(kcase) printf("\n");
read();
solve();
}
return ;
}
上一篇:老李分享:《Java Performance》笔记1——性能分析基础 1


下一篇:构建自己的PHP框架--构建模版引擎(2)