从给定的那些去除广告牌 [英] Removal of billboards from given ones

问题描述

我碰到这个问题。

  

ADZEN是一个非常受欢迎的广告公司在你的城市。在每路   你可以看到他们的广告牌。最近，他们正面临着   严峻的挑战，MG路最常用和美丽的道路在你的   全市已几乎坐满了广告牌，这是有一个   对
负面影响       自然景观。           在人们的需求ADZEN已决定取消一些广告牌        在这样一种方式，有没有更多于K广告牌一起站在       任何部分之路。           你可以假设MG路是用N billboards.Initially直线有任何两个adjecent之间没有间隙   广告牌。           ADZEN的主要收入来自这些广告牌所以广告牌去除处理，必须以这样一种方式，完成   广告牌       留在到底应该给予最大可能的利润之间的配置的所有可能的最终configurations.Total利润是   所有广告牌present在利润值的总和   组态。           给定N，K和每个N个广告牌，输出，可以从剩余获得最大利润的利润值   给出的条件下的广告牌。

     

输入说明

     

1号线包含两个空间分隔的整数N和K.然后按照描述每个广告牌，即第i个利润值N线   行包含第i个广告牌的利润价值。

 采样输入
    6 2
    1
    2
    3
    1
    6
    10

    样本输出
    21
 

     

说明

     

在给定的输入有6个广告牌和后工序不超过2个应该在一起。因此，除去第一和第四   广告牌给人一种配置_ 2 3 _ 6 10，其具有利润21。   没有其他的配置具有盈利超过21.So答案是21。

 约束
    1＆LT; = N＆LT; = 1,00,000（10 ^ 5）
    1＆LT; = K＆LT; = N
    = 20亿（2 * 10 ^ 9）; 0℃下，任何广告牌＆LT的=利润价值
 

我认为，我们必须在第一K + 1板选择最低成本板，然后重复同样的，直到最后，但是这并没有给予正确的答案 对于所有的情况下。 我试图高达我的知识，但无法找到解决办法。         如果任何一个有想法请您分享您的thougths。

解决方案

这是一个典型的DP问题。让我们说，P（n，k）是具有k个广告牌到道路上的位置n的最大利润。那么你有以下的公式：

  P（N，K）= MAX（P（N-1，K），P（N-1，K-1）+ C（N））
 P（I，0）= 0对于i = 0到n
 

其中c（n）是从把第n个广告牌的道路上的利润。使用这个公式来计算P（N，K）自​​下而上你会得到O（NK）时间的解决方案。

我将离开你来弄清楚为什么这个公式成立。

修改

荡，我误解了问题。

它仍然是一个DP问题，只是公式是不同的。比方说，P（V，I）是指在点V最大的利润，其中广告牌的最后一个簇的大小为我。 那么P（V，I），可以使用下面的公式描述：

  P（V，I）= P（V-1，Ⅰ-1）+ C（五）如果我＆GT; 0
P（V，0）=最大（P（V-1，ⅰ）对于i = 0..min（K，V））
P（0,0）= 0
 

您需要找到 MAX（P（N，I），其中i = 0..k））。

I came across this question

ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on
the natural view. On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road. You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards. ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration. Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.

Input description

1st line contain two space seperated integers N and K. Then follow N lines describing the profit value of each billboard i.e ith line contains the profit value of ith billboard.

    Sample Input
    6 2 
    1
    2
    3
    1
    6
    10 

    Sample Output
    21

Explanation

In given input there are 6 billboards and after the process no more than 2 should be together. So remove 1st and 4th billboards giving a configuration _ 2 3 _ 6 10 having a profit of 21. No other configuration has a profit more than 21.So the answer is 21.

    Constraints
    1 <= N <= 1,00,000(10^5)
    1 <= K <= N
    0 <= profit value of any billboard <= 2,000,000,000(2*10^9)

I think that we have to select minimum cost board in first k+1 boards and then repeat the same untill last,but this was not giving correct answer for all cases. i tried upto my knowledge,but unable to find solution. if any one got idea please kindly share your thougths.

解决方案

It's a typical DP problem. Lets say that P(n,k) is the maximum profit of having k billboards up to the position n on the road. Then you have following formula:

 P(n,k) = max(P(n-1,k), P(n-1,k-1) + C(n))
 P(i,0) = 0 for i = 0..n

Where c(n) is the profit from putting the nth billboard on the road. Using that formula to calculate P(n, k) bottom up you'll get the solution in O(nk) time.

I'll leave up to you to figure out why that formula holds.

edit

Dang, I misread the question.

It still is a DP problem, just the formula is different. Let's say that P(v,i) means the maximum profit at point v where last cluster of billboards has size i. Then P(v,i) can be described using following formulas:

P(v,i) = P(v-1,i-1) + C(v) if i > 0 
P(v,0) = max(P(v-1,i) for i = 0..min(k, v)) 
P(0,0) = 0

You need to find max(P(n,i) for i = 0..k)).

这篇关于从给定的那些去除广告牌的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！