# 算法设计：公路广告牌问题解决和代码实现

## 本文概述

``````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}首先, 在继续解决方案之前。

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
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
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 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
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
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``

https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture18/Lecture18.pdf

• 回顶