srcmini本文概述
考虑一条高速公路中号英里。任务是在高速公路上放置广告牌, 以使收入最大化。广告牌可能的位置由数字给出X1<x2<….. <xn-1<xñ, 以从路段的一端开始的英里为单位指定位置。如果我们将广告牌放置在位置x一世, 我们获得了[R一世> 0。有一个限制, 即不能在其中放置两个广告牌Ť英里以下。
注意：所有来自x的网站1到xñ需要在M英里的高速公路上放置广告牌, 范围是0到M。
例子：
Input : M = 20
x[] = {6, 7, 12, 13, 14}
revenue[] = {5, 6, 5, 3, 1}
t = 5
Output: 10
By placing two billboards at 6 miles and 12
miles will produce the maximum revenue of 10.
Input : M = 15
x[] = {6, 9, 12, 14}
revenue[] = {5, 6, 3, 7}
t = 2
Output : 18推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。
令maxRev [i], 1 <= i <= M, 是从高速公路开始到i英里所产生的最大收益。现在, 对于高速公路上的每一英里, 我们需要检查该英里是否可以选择任何广告牌, 否则, 直到该英里之前产生的最大收入将与直到一英里之前产生的最大收入相同。但是, 如果该英里有广告牌选项, 那么我们有2个选项：
1.我们要么放置广告牌, 要么忽略前t英里内的广告牌, 然后添加所放置广告牌的收入。
2.忽略此广告牌。因此, maxRev [i] = max(maxRev [i-t-1] +收入[i], maxRev [i-1])
以下是此方法的实现：
C ++
// C++ program to find maximum revenue by placing
// billboard on the highway with given constarints.
#include<bits/stdc++.h>
using namespace std;
int maxRevenue( int m, int x[], int revenue[], int n, int t)
{
// Array to store maximum revenue at each miles.
int maxRev[m+1];
memset (maxRev, 0, sizeof (maxRev));
// actual minimum distance between 2 billboards.
int nxtbb = 0;
for ( int i = 1; i <= m; i++)
{
// check if all billboards are already placed.
if (nxtbb < n)
{
// check if we have billboard for that particular
// mile. If not, copy the previous maximum revenue.
if (x[nxtbb] != i)
maxRev[i] = maxRev[i-1];
// we do have billboard for this mile.
else
{
// We have 2 options, we either take current
// or we ignore current billboard.
// If current position is less than or equal to
// t, then we can have only one billboard.
if (i <= t)
maxRev[i] = max(maxRev[i-1], revenue[nxtbb]);
// Else we may have to remove previously placed
// billboard
else
maxRev[i] = max(maxRev[i-t-1]+revenue[nxtbb], maxRev[i-1]);
nxtbb++;
}
}
else
maxRev[i] = maxRev[i - 1];
}
return maxRev[m];
}
// Driven Program
int main()
{
int m = 20;
int x[] = {6, 7, 12, 13, 14};
int revenue[] = {5, 6, 5, 3, 1};
int n = sizeof (x)/ sizeof (x[0]);
int t = 5;
cout << maxRevenue(m, x, revenue, n, t) << endl;
return 0;
}Java
// Java program to find maximum revenue
// by placing billboard on the highway
// with given constarints.
class GFG
{
static int maxRevenue( int m, int [] x, int [] revenue, int n, int t)
{
// Array to store maximum revenue
// at each miles.
int [] maxRev = new int [m + 1 ];
for ( int i = 0 ; i < m + 1 ; i++)
maxRev[i] = 0 ;
// actual minimum distance between
// 2 billboards.
int nxtbb = 0 ;
for ( int i = 1 ; i <= m; i++)
{
// check if all billboards are
// already placed.
if (nxtbb < n)
{
// check if we have billboard for
// that particular mile. If not, // copy the previous maximum revenue.
if (x[nxtbb] != i)
maxRev[i] = maxRev[i - 1 ];
// we do have billboard for this mile.
else
{
// We have 2 options, we either take
// current or we ignore current billboard.
// If current position is less than or
// equal to t, then we can have only
// one billboard.
if (i <= t)
maxRev[i] = Math.max(maxRev[i - 1 ], revenue[nxtbb]);
// Else we may have to remove
// previously placed billboard
else
maxRev[i] = Math.max(maxRev[i - t - 1 ] +
revenue[nxtbb], maxRev[i - 1 ]);
nxtbb++;
}
}
else
maxRev[i] = maxRev[i - 1 ];
}
return maxRev[m];
}
// Driver Code
public static void main(String []args)
{
int m = 20 ;
int [] x = new int []{ 6 , 7 , 12 , 13 , 14 };
int [] revenue = new int []{ 5 , 6 , 5 , 3 , 1 };
int n = x.length;
int t = 5 ;
System.out.println(maxRevenue(m, x, revenue, n, t));
}
}
// This code is contributed by Ita_c.Python3
# Python3 program to find maximum revenue
# by placing billboard on the highway with
# given constarints.
def maxRevenue(m, x, revenue, n, t) :
# Array to store maximum revenue
# at each miles.
maxRev = [ 0 ] * (m + 1 )
# actual minimum distance between
# 2 billboards.
nxtbb = 0 ;
for i in range ( 1 , m + 1 ) :
# check if all billboards are
# already placed.
if (nxtbb < n) :
# check if we have billboard for
# that particular mile. If not, # copy the previous maximum revenue.
if (x[nxtbb] ! = i) :
maxRev[i] = maxRev[i - 1 ]
# we do have billboard for this mile.
else :
# We have 2 options, we either take
# current or we ignore current billboard.
# If current position is less than or
# equal to t, then we can have only
# one billboard.
if (i < = t) :
maxRev[i] = max (maxRev[i - 1 ], revenue[nxtbb])
# Else we may have to remove
# previously placed billboard
else :
maxRev[i] = max (maxRev[i - t - 1 ] +
revenue[nxtbb], maxRev[i - 1 ]);
nxtbb + = 1
else :
maxRev[i] = maxRev[i - 1 ]
return maxRev[m]
# Driver Code
if __name__ = = "__main__" :
m = 20
x = [ 6 , 7 , 12 , 13 , 14 ]
revenue = [ 5 , 6 , 5 , 3 , 1 ]
n = len (x)
t = 5
print (maxRevenue(m, x, revenue, n, t))
# This code is contributed by RyugaC#
// C# program to find maximum revenue
// by placing billboard on the highway
// with given constarints.
using System;
class GFG
{
static int maxRevenue( int m, int [] x, int [] revenue, int n, int t)
{
// Array to store maximum revenue
// at each miles.
int [] maxRev = new int [m + 1];
for ( int i = 0; i < m + 1; i++)
maxRev[i] = 0;
// actual minimum distance between
// 2 billboards.
int nxtbb = 0;
for ( int i = 1; i <= m; i++)
{
// check if all billboards are
// already placed.
if (nxtbb < n)
{
// check if we have billboard for
// that particular mile. If not, // copy the previous maximum revenue.
if (x[nxtbb] != i)
maxRev[i] = maxRev[i - 1];
// we do have billboard for this mile.
else
{
// We have 2 options, we either take
// current or we ignore current billboard.
// If current position is less than or
// equal to t, then we can have only
// one billboard.
if (i <= t)
maxRev[i] = Math.Max(maxRev[i - 1], revenue[nxtbb]);
// Else we may have to remove
// previously placed billboard
else
maxRev[i] = Math.Max(maxRev[i - t - 1] +
revenue[nxtbb], maxRev[i - 1]);
nxtbb++;
}
}
else
maxRev[i] = maxRev[i - 1];
}
return maxRev[m];
}
// Driver Code
static void Main()
{
int m = 20;
int [] x = new int []{6, 7, 12, 13, 14};
int [] revenue = new int []{5, 6, 5, 3, 1};
int n = x.Length;
int t = 5;
Console.Write(maxRevenue(m, x, revenue, n, t));
}
}
// This code is contributed by DrRoot_的PHP
<?php
// PHP program to find
// maximum revenue by
// placing billboard on
// the highway with given
// constraints.
function maxRevenue( $m , $x , $revenue , $n , $t )
{
// Array to store maximum
// revenue at each miles.
$maxRev = array_fill (0, $m + 1, false);
// actual minimum distance
// between 2 billboards.
$nxtbb = 0;
for ( $i = 1; $i <= $m ; $i ++)
{
// check if all billboards
// are already placed.
if ( $nxtbb < $n )
{
// check if we have billboard
// for that particular
// mile. If not, copy the
// previous maximum revenue.
if ( $x [ $nxtbb ] != $i )
$maxRev [ $i ] = $maxRev [ $i - 1];
// we do have billboard
// for this mile.
else
{
// We have 2 options, // we either take
// current or we ignore
// current billboard.
// If current position is
// less than or equal to
// t, then we can have only
// one billboard.
if ( $i <= $t )
$maxRev [ $i ] = max( $maxRev [ $i - 1], $revenue [ $nxtbb ]);
// Else we may have to
// remove previously
// placed billboard
else
$maxRev [ $i ] = max( $maxRev [ $i - $t - 1] +
$revenue [ $nxtbb ], $maxRev [ $i - 1]);
$nxtbb ++;
}
}
else
$maxRev [ $i ] = $maxRev [ $i - 1];
}
return $maxRev [ $m ];
}
// Driver Code
$m = 20;
$x = array (6, 7, 12, 13, 14);
$revenue = array (5, 6, 5, 3, 1);
$n = sizeof( $x );
$t = 5;
echo maxRevenue( $m , $x , $revenue , $n , $t );
// This code is contributed by ajit
?>输出如下：
10时间复杂度：O(M), 其中M是公路总距离。
辅助空间：O(M)。
资源 ：
https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture18/Lecture18.pdf
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
评论前必须登录！
注册