公路广告牌问题-yiteyi-C++库

考虑一条高速公路 M 英里。我们的任务是在高速公路上放置广告牌，以实现收入最大化。广告牌的可能位置按数字给出 十、 _1. 2. < ….. < 十、 _n-1 N ，以英里为单位指定从道路一端测量的位置。如果我们在x位置放一个广告牌 _我，我们的收入为 R _我 > 0 .有一项限制规定，在该区域内不得放置两块广告牌 T 英里或更少。注意：所有可能的站点都来自x _1. 到x _N 范围从0到M，因为需要在M英里的高速公路上放置广告牌。 例如：

null

Input : M = 20        x[]       = {6, 7, 12, 13, 14}        revenue[] = {5, 6, 5,  3,  1}        t = 5Output: 10By placing two billboards at 6 miles and 12miles will produce the maximum revenue of 10.Input : M = 15        x[] = {6, 9, 12, 14}        revenue[] = {5, 6, 3, 7}        t = 2Output : 18

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

假设maxRev[i]，1<=i<=M，是从开始到在高速公路上行驶i英里所产生的最大收入。现在，对于高速公路上的每一英里，我们需要检查这一英里是否有任何广告牌的选项，如果没有，那么直到这一英里的最大收入将与直到前一英里的最大收入相同。但如果那一英里有广告牌选项，那么我们有两个选项： 1.要么我们放置广告牌，忽略之前t英里中的广告牌，然后添加放置广告牌的收入。 2.忽略这个广告牌。所以maxRev[i]=max（maxRev[i-t-1]+revenue[i]，maxRev[i-1]）以下是该方法的实施：

C++

                         // C++ program to find maximum revenue by placing                       
                         // billboard on the highway with given constraints.                       
                         #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 constraints.                       
           
                         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 constraints.                       
           
                         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 Ryuga                       

C#

                         // C# program to find maximum revenue                       
                         // by placing billboard on the highway                       
                         // with given constraints.                       
                         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                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript 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.                       
                                                 let maxRev =                                     new                                     Array(m + 1);                       
                                                 for                                     (let i = 0; i < m + 1; i++)                       
                                                 maxRev[i] = 0;                       
                                   
                                                 // actual minimum distance between                       
                                                 // 2 billboards.                       
                                                 let nxtbb = 0;                       
                                                 for                                     (let 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                       
                                                 let  m = 20;                       
                                                 let x=[6, 7, 12, 13, 14];                       
                                                 let revenue=[5, 6, 5, 3, 1];                       
                                                 let n = x.length;                       
                                                 let t = 5;                       
                                                 document.write(maxRevenue(m, x, revenue, n, t));                       
                                   
                                                 // This code is contributed by rag2127                       
           
                         </script>                       

输出：

时间复杂性： O（M），其中M是整个公路的距离。 辅助空间： O（M）。 资料来源： https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture18/Lecture18.pdf 本文由 阿努伊·乔汉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章