沈阳学网站制作学校,小组网站建设方案书,wordpress设置cdn缓存过期配置,北京网站建设最大的公司排名题意#xff1a;有三个火车头#xff0c;n个车厢#xff0c;每个车厢里面对应的有一定的人数。规定每个火车头最多 拉m个连续的车厢而且他们拉的车厢一定是从左到右连续的#xff0c;问它能够拉的最多的人数#xff1b;
思路#xff1a;类似01背包的解法#xff0c;首先…题意有三个火车头n个车厢每个车厢里面对应的有一定的人数。规定每个火车头最多 拉m个连续的车厢而且他们拉的车厢一定是从左到右连续的问它能够拉的最多的人数
思路类似01背包的解法首先每个火车最多拉m个连续的车厢这里我们把只要存在 连续的m个车厢的就看成一个物品。相当于往背包容量为3的背包里面放物品所得的最 大价值量。但是这里注意每连续的m个车厢为一个物品 f[i][j] max(f[i - 1][j],f[i - m][j - 1] sum[i] - sum[i - m]); 这里对于每个物品要么不放要么就是放放连续的m个车厢 sum[i] a[0] a[1] ... a[i]; 之前看到这个解题思路感觉一点有疑问会不会有重复第一节拉12第二节拉 2,3这样的最后结论是不会;因为不取这个车厢的话那必然就是【i-1】【j】, 如果取的话那么肯定就是【i-m】【j-1】,跳到了i-m了所以不会重
Time limit 1000 ms
Memory limit 30000 kB
OS Linux
Source Tehran Sharif 2004 Preliminary
B - A Mini Locomotive POJ - 1976
A train has a locomotive that pulls the train with its many passenger coaches. If the locomotive breaks down, there is no way to pull the train. Therefore, the office of railroads decided to distribute three mini locomotives to each station. A mini locomotive can pull only a few passenger coaches. If a locomotive breaks down, three mini locomotives cannot pull all passenger coaches. So, the office of railroads made a decision as follows: 1. Set the number of maximum passenger coaches a mini locomotive can pull, and a mini locomotive will not pull over the number. The number is same for all three locomotives. 2. With three mini locomotives, let them transport the maximum number of passengers to destination. The office already knew the number of passengers in each passenger coach, and no passengers are allowed to move between coaches. 3. Each mini locomotive pulls consecutive passenger coaches. Right after the locomotive, passenger coaches have numbers starting from 1. For example, assume there are 7 passenger coaches, and one mini locomotive can pull a maximum of 2 passenger coaches. The number of passengers in the passenger coaches, in order from 1 to 7, is 35, 40, 50, 10, 30, 45, and 60. If three mini locomotives pull passenger coaches 1-2, 3-4, and 6-7, they can transport 240 passengers. In this example, three mini locomotives cannot transport more than 240 passengers. Given the number of passenger coaches, the number of passengers in each passenger coach, and the maximum number of passenger coaches which can be pulled by a mini locomotive, write a program to find the maximum number of passengers which can be transported by the three mini locomotives.
Input
The first line of the input contains a single integer t (1 t 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows: The first line of the input file contains the number of passenger coaches, which will not exceed 50,000. The second line contains a list of space separated integers giving the number of passengers in each coach, such that the i thnumber of in this line is the number of passengers in coach i. No coach holds more than 100 passengers. The third line contains the maximum number of passenger coaches which can be pulled by a single mini locomotive. This number will not exceed 1/3 of the number of passenger coaches.
Output
There should be one line per test case, containing the maximum number of passengers which can be transported by the three mini locomotives.
Sample Input
1
7
35 40 50 10 30 45 60
2Sample Output
240
题意有三个火车头n个车厢每个车厢里面对应的有一定的人数。规定每个火车头最多 拉m个连续的车厢而且他们拉的车厢一定是从左到右连续的问它能够拉的最多的人数
思路类似01背包的解法首先每个火车最多拉m个连续的车厢这里我们把只要存在 连续的m个车厢的就看成一个物品。相当于往背包容量为3的背包里面放物品所得的最 大价值量。但是这里注意每连续的m个车厢为一个物品 f[i][j] max(f[i - 1][j],f[i - m][j - 1] sum[i] - sum[i - m]); 这里对于每个物品要么不放要么就是放放连续的m个车厢 sum[i] a[0] a[1] ... a[i]; 之前看到这个解题思路感觉一点有疑问会不会有重复第一节拉12第二节拉 2,3这样的最后结论是不会;因为不取这个车厢的话那必然就是【i-1】【j】, 如果取的话那么肯定就是【i-m】【j-1】,跳到了i-m了所以不会重
#includeiostream
#includealgorithm
#includestring.h
using namespace std;
int m,n,w[50010],dp[4][50010],s[50010];
int main()
{int t;cint;while(t--){cinm;memset(s,0,sizeof(s));for(int i1; im; i){cinw[i];s[i]s[i-1]w[i];}cinn;memset(dp,0,sizeof(dp));for(int i1; i3; i)//对于每段max车厢都有拉或不拉两种情况for(int jn; jm; j)//但是需要比较的不是前一次最多可拉多少乘客因为这样被选车厢有冲突dp[i][j]max(dp[i][j-1],dp[i-1][j-n]s[j]-s[j-n]);/*所以需要和前max次比较。*/coutdp[3][m]endl;}return 0;
}
/*题意概括在车站有的时候需要用迷你火车头来拉乘客现在知道车站
有3个迷你火车头给出每个迷你火车头可以拉几节车厢已经n个车厢即
每个车厢的乘客数小火车必须拉连续的车厢乘客不能换车厢。问3个
迷你火车头最多能拉多少乘客
解题思路看完题也能想到这是一个贪心的问题。首先可以根据给出的火
车头最多拉车厢的数max算出每max节车厢有多少乘客然后对这些连续的
max车厢的乘客数进行选择但是如果选择一段车厢那么后面算出的max
节车厢会有冲突需要把这些冲突的车厢跳过去。关键就是要退出状态转
移方程这题和01背包类似*/
