正文

noi6045开餐馆

谦谦君子，陌上其华  谦谦君子，陌上其华  2022-08-22  258

关键词：

http://noi.openjudge.cn/ch0206/6045/

描述

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m₁, m₂, ... m_n 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用p_i 表示在m_i 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

输入标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行,
第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000).
第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列)
第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数)输出对于每组测试数据可能的最大利润

样例输入

样例输出

40
30

思路：

d[i]表示分析到第i个地点时可以获得的最大利润。其实题目不难，看代码应该能懂得。

 1 #include<iostream> 
 2 #include<string>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int n, k;
 8 
 9 int m[105];
10 int p[105];
11 int d[105];
12 
13 int main()
14 {
15     //freopen("D:\txt.txt", "r", stdin);
16     int T;
17     scanf("%d", &T);
18     while (T--)
19     {
20         cin >> n >> k;
21         for (int i = 0; i < n; i++)
22             cin >> m[i];
23         for (int i = 0; i < n; i++)
24             cin >> p[i];
25         for (int i = 0; i < n; i++)
26         {
27             d[i] = max(d[i - 1], p[i]);
28             for (int j = i-1; j >= 0; j--)
29             {
30                 if (m[i] - m[j] > k)
31                     d[i] = max(d[i], d[j] + p[i]);
32             }
33         }
34         cout << d[n-1] << endl;
35     }
36     return 0;
37 }

6045:开餐馆

/*//http://noi.openjudge.cn/ch0206/6045/ 6045:开餐馆查看提交统计提问总时间限制:1000ms内存限制:65536kB 描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的... 查看详情

openjudge6045:开餐馆(代码片段)

描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1,m2,...mn 来表示他们的相对... 查看详情

开餐馆

6045:开餐馆总时间限制: 1000ms 内存限制: 65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线... 查看详情

004:开餐馆

004:开餐馆总时间限制:1000ms内存限制:65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这n个地点排列在同一条直线上。我们用一个整数序列m1,m2... 查看详情

bailian4118开餐馆dp(代码片段)

4118:开餐馆总时间限制:1000ms内存限制:65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这n个地点排列在同一条直线上。我们用一个整数序列m1,m... 查看详情

动规(12)-开餐馆(代码片段)

描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这n个地点排列在同一条直线上。我们用一个整数序列m1,m2,...mn来表示他们的相对位置。由于地段关... 查看详情

动规(12)-开餐馆(代码片段)

开餐馆

...p;65536kB描述北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1,m2,...mn 来表示他们... 查看详情

小说脑洞：《我在伊拉克开餐馆的日子》

...作战失败，而后引咎辞职，离开了祖国，到伊拉克开一家餐馆。风格：黑暗流。篇幅：中短篇。开篇：他唯一执行任务失败的一次，也就是导致他引咎辞职的任务。他领导一队特种兵，一共二... 查看详情

智能电视赛道，已成tcl小米华为等贴身肉搏的擂台

...商业街，如果来的是犹太人，A会开修车行、B会开餐馆、C会开超市……总之不同的犹太人会做不一样的生意。而如果来的是中国人，A开了家餐馆生意火爆，然后B、C、D、E……都会争相开餐馆。虽然这是个老段子&#... 查看详情

noi2017划水记

Day-2听说我能来NOI（捂脸熊xy说我肩负重任（奶的漂亮），要MAKEXJGREATAGAIN（大雾感觉我已经沦为暴力隔膜选手了啊…… Day-1报到日早上开supermeatboy，把第5张图推的差不多了……然而我并没有把它拷出来，绍兴... 查看详情

hdu6045isdereklying?（思维推导）

ProblemDescriptionDerekandAlfiaaregoodfriends.DerekisChinese,andAlfiaisAustrian.Thissummerholiday,theybothparticipateinthesummercampofBorussiaDortmund.Duringthesummercamp,therewillbefantestsatinterval 查看详情

bzoj3670:[noi2014]动物园

题面传送门Sol这是一道阅读理解题，读了好久才明白意思。。。首先可以想到处理出next数组，每次的位置i跳next跳到长度小于i的一半位置，然后继续跳到零统计此时跳的次数就是答案那么暴力就是(O(n^2))让我们一起膜拜yyb大佬的... 查看详情

hdu6045多校签到题目

http://acm.hdu.edu.cn/showproblem.php?pid=6045题解：遍历一遍，求出两个人答案中相同的个数，用wa表示。然后我从大的数入手，当wa的数都尽可能在两个人答案的相同部分时，另一个人的答案中对的个数最小；当wa的数尽可能在两者答案... 查看详情

超级钢琴2010年noi

/*自己yy的奇葩做法居然A了23333不过空间好像很大时间好像略慢.....毕竟不是正解前缀维护sum值枚举区间起点然后终点的坐标可以确定在一个范围可持久化线段树查询区间第1大然后放到堆里注意每个从堆里取出来再把这个区间第2... 查看详情

loj6045「雅礼集训2017day8」价

传送门：https://loj.ac/problem/6045【题解】由于存在完美匹配，所以选择k个药就要选择>=k个药材，我们要求的是选择k个药正好选择k个药材。那么定义选一种减肥药的代价为-pi+INF，选一种药材的代价为INF，这样最小割肯定是恰好... 查看详情

餐馆最短距离

有个N叉树是个大食堂的地图。节点有的是餐馆，有的不是，在输入里面用boolean表示了。每个父节点到子节点的距离都是一。你作为一个吃货，从根节点出发，要去所有的餐馆尝尝，需要的最短路径是多少。楼主DFS返回两个量，... 查看详情