ITKeyword,专注技术干货聚合推荐

注册 | 登录

百练 开餐馆

q547550831 分享于 2016-07-31

推荐:POJ 1011 Sticks (DFS + 剪枝)

题目大意: 原来有很多根相同长度的木棒。乔治把这些木棒随意切成了  给出的长度。 问你他原来带来的那些相同长度的木棒的长度。 这个长度要最小。 思路: 强剪枝

2020腾讯云“6.18”活动开始了!!!(巨大优惠重现!4核8G,5M带宽 1999元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1059

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

百练 开餐馆


总时间限制: 内存限制:
1000ms 65536kB

描述

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

推荐:noip2012 文化之旅 (深搜,最优性剪枝)

P2070 [NOIP2012P4]文化之旅 时间: 1000ms / 空间: 131072KiB / Java类名: Main 背景 NOIP 2012 普及组 题4 描述 有一位使者要游历各国,他每到一个国家,都能学

输入

标准的输入包含若干组测试数据。输入第一行是整数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 且为整数)

输出

对于每组测试数据可能的最大利润

样例输入

2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30

样例输出

40
30

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_NUM = 1000 + 5;

int n;
int dis[MAX_NUM];
int pro[MAX_NUM];
int k;
int ans;
int maxP[MAX_NUM];

void dfs(int id, int p) {
    if(dis[id] + k >= dis[n - 1]) {
        ans = max(p, ans);
        return;
    }

    for(int i = id + 1; i < n; i++) {
        // 最优性剪枝
        // 到当前位置的最大值已不大于记录的到当前位置的值
        if(dis[i] - dis[id] > k && p + pro[i] > maxP[i]) {
            maxP[i] = p + pro[i];
            dfs(i, p + pro[i]);
        }
    }
}

int main() {
    int kase;
    scanf("%d", &kase);
    while(kase--) {
        memset(dis, 0, sizeof(dis));
        memset(pro, 0, sizeof(pro));
        memset(maxP, 0, sizeof(maxP));
        ans = 0;
        scanf("%d%d", &n, &k);
        for(int i = 0; i < n; i++) {
            scanf("%d", &dis[i]);
        }
        for(int i = 0; i < n; i++) {
            scanf("%d", &pro[i]);
        }
        for(int i = 0; i < n; i++) {
            dfs(i, pro[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

推荐:poj 1011 Sticks 【DFS】+【剪枝】

题意:有未知根(长度一样)木棒(小于等于n),被猪脚任意的截成n段,猪脚(脑抽了)想知道被截之前的最短长度(我推测猪脚得了健忘症)。 这道题光理解题意就

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

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。