本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
注意:所有来自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 + = 1else :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 Ryuga
C#
// 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
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- Linux中的HISTCONTROL命令及示例
- 2021年8个顶级Node.js框架推荐,Web开发必备干货!
- 如何在JavaScript中实现HashMap(详细实现指南)
- 删除不必要的启动条目并加快启动速度的4个工具
- 如果有智慧公交可视化平台,《开端》还能无限重启吗()
- 用于Windows关机,休眠,睡眠或重启的8个免费工具
- 用于防止Windows关机,休眠,睡眠或重启的8个免费工具
- Linux之RPM包管理_安装升级与卸载
- 从新计算机中删除预装软件的 5 个工具