Ruratania is just entering capitalism and is establishing new enterprising activities in many fields including transport. The transportation company TransRuratania is starting a new express train from city A to
city B with several stops in the stations on the way. The stations are successively numbered, city A station has number 0, city B station numberm. The company runs an experiment in order to improve passenger transportation capacity and thus to increase
its earnings. The train has a maximum capacitynpassengers. The price of the train ticket is equal to the number of stops (stations) between the starting station and the destination station (including the destination station). Before the train starts
its route from the city A, ticket orders are collected from all onroute stations. The ticket order from the station S means all reservations of tickets from S to a fixed destination station. In case the company cannot accept all orders because of the passenger
capacity limitations, its rejection policy is that it either completely accept or completely reject single orders from single stations.
Write a program which for the given list of orders from single stations on the way from A to B determines the biggest possible total earning of the TransRuratania company. The earning from one accepted order is
the product of the number of passengers included in the order and the price of their train tickets. The total earning is the sum of the earnings from all accepted orders.
Input
The input file is divided into blocks. The first line in each block contains three integers: passenger capacitynof the train, the number of the city B station and the number of ticket orders from all
stations. The next lines contain the ticket orders. Each ticket order consists of three integers: starting station, destination station, number of passengers. In one block there can be maximum 22 orders. The number of the city B station will be at most 7.
The block where all three numbers in the first line are equal to zero denotes the end of the input file.
Output
The output file consists of lines corresponding to the blocks of the input file except the terminating block. Each such line contains the biggest possible total earning.
Sample Input
10 3 4
0 2 1
1 3 5
1 2 7
2 3 10
10 5 4
3 5 10
2 4 9
0 2 5
2 5 8
0 0 0
Sample Output
19
34
这道题用数组标记回溯会超时。我第一次就因为这个超时了,改成现在这种方法就AC了
#include<iostream>
#include<cstring>
using namespace std;
int order[30][5];
int vis[30],place[10];
int maxnum,n,m,t;
int judge(int pos)
{
int tag=1;
int k;
for(k=order[pos][0];k<order[pos][1];k++)
{
if(order[pos][2]+place[k]>n)
{
tag=0;
break;
}
}
return tag;
}
void dfs(int pos,int ans)
{
if(ans>maxnum) maxnum=ans;
if(pos>=t) return;
int i;
if(judge(pos))
{
for(i=order[pos][0];i<order[pos][1];i++)
place[i]=place[i]+order[pos][2];
dfs(pos+1,ans+(order[pos][1]-order[pos][0])*order[pos][2]);
for(i=order[pos][0];i<order[pos][1];i++)
place[i]=place[i]-order[pos][2];
}
dfs(pos+1,ans);
}
int main()
{
while(cin>>n>>m>>t&&(n||m||t))
{
int i,j;
if(!n||!m||!t)
{
cout<<"0"<<endl;
continue;
}
memset(order,0,sizeof(order));
memset(place,0,sizeof(place));
for(i=0;i<t;i++)
cin>>order[i][0]>>order[i][1]>>order[i][2];
maxnum=0;
dfs(0,0);
cout<<maxnum<<endl;
}
return 0;
}
分享到:
相关推荐
Transportation
Intelligent Transportation Systems.pdf
ajax_transportation_methods 官方文档
transportation
good child 关于gis-t 发展状态的认识,分为 map view、 navi view、 behievid view gis transportation
航运模型 Air Transportation Modeling and Sim
This book aims at giving a broad introduction into the basic but relevant concepts related to transportation systems, targeting researchers and practitioners from computer science and information ...
-Challenges and opportunities in transportation AI --Overview of urban transportation --The emerging challenges in transportation AI -AI applications in transportation -Data and tools for ...
SAP公司运输管理系统TM(Transportation Managemtn)的基础设置文档
Resilience and efficiency in transportation networks外文文献翻译,和别人合作翻译的,有专业名词不准确,原文在上一篇。
Emergency Care and Transportation of the Sick and Injured 11th Edition
Intelligent Transportation Systems (ITSs) are envisioned to play a critical role in improving traffic flow and reducing congestion, which is a pervasive issue impact ing urban areas around the globe. ...
ocrale教材,讲的还可以,可以做为一本教材使用
珍贵的TRB论文,很难得的。共享一下,交流交流。
外文文献Resilience and efficiency in transportation networks,翻译在下一篇。
Transportation运输.ppt
tcp is the transportation control protocle code
jsp调用ajax技术的详细讲解与分析。PPT版本的。
Big Data in Transportation
面对日益严峻的疫情防控形势,交通运输作为疫情防控的第一道防线自然不能懈怠。通过对四川市各个区县来自湖北、武汉、重庆的入境出境的公路检查点、人数、车辆的对比分析来对四川市进行有效的控制病情的传播。...