点击打开链接
题目意思: 有一辆车从A城市开往B城市,途中有m个站,车上最多的载客人数为n人,每一个站的价格就是终点和起点的差值,现在有k分订单,要求找到这辆车的最大利润
解题思路: 这一题如果我们去搜索站点,那么情况将会非常糟糕,但是如果我么去搜索订单,那么对于每一个订单而言就是取和不取,那么我们就可以知道这个解空间树的每一层就是一个订单,那么我们只要对这个订单编号,然后搜索订单即可。另外我们开一个数组,专门来存储每一个站点当前的人数,注意这里的人数处理,一份订单进来,那么起点---终点前一站都是要加上的,终点下车不用加,还有做dfs之前都是先判断judge函数,最后恢复现场。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAXN = 25;
int n, m, d;
int num[10]; //记录每一个站点的人数
int ans;
struct Order {//订单的结构体,存储起点和终点和人数
int start;
int end;
int number;
};
Order o[MAXN];//结构体数组
//判断当前的所有的站点的人数是否
int judge() {
for(int i = 0 ; i <= m ; i++){
if(num[i] > n)//如果人数大于n则不满足
return 0;
}
return 1;
}
void dfs(int k , int max) {
if(ans < max)
ans = max;
while(k < d){
//如果要选择该订单
for(int i = o[k].start ; i < o[k].end ; i++)
num[i] += o[k].number;
if(judge())
dfs(k+1 , max+o[k].number*(o[k].end-o[k].start));
//由于之前就加上了人数,所以这里一定要减去人数
for(int i = o[k].start ; i < o[k].end ; i++)
num[i] -= o[k].number;
++k;//下一个订单
}
}
//
int main() {
while (scanf("%d%d%d%*c", &n, &m, &d)) {
if( n == 0 && m == 0 && d == 0)//注意是 0 0 0 结束
break;
memset(num, 0, sizeof (num));
ans = 0;
for (int i = 0; i < d; i++)
scanf("%d%d%d", &o[i].start, &o[i].end, &o[i].number);
dfs(0, 0);
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC