动态规划|建造桥梁-yiteyi-C++库

考虑一个二维地图，一个水平河流通过它的中心。南岸有n座城市，x坐标为a（1）…a（n），北岸有n座城市，x坐标为b（1）…b（n）。你想用桥梁连接尽可能多的南北城市，这样就不会有两座桥梁交叉。连接城市时，只能将北岸的城市a（i）连接到南岸的城市b（i）。可建造的最大桥梁数量，以连接具有上述约束条件的南北对。

null

上岸的值可被视为城市的北x坐标，下岸的值可被视为与北x坐标城市相连的城市的相应南x坐标。例如：

Input : 6 4 2 1        2 3 6 5Output : Maximum number of bridges = 2Explanation: Let the north-south x-coordinatesbe written in increasing order.1  2  3  4  5  6                 For the north-south pairs             (2, 6) and (1, 5)             the bridges can be built.             We can consider other pairs also,             but then only one bridge can be built              because more than one bridge built will             then cross each other.            1  2  3  4  5  6 Input : 8 1 4 3 5 2 6 7         1 2 3 4 5 6 7 8Output : Maximum number of bridges = 5

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

方法： 它是利斯问题以下是解决问题的步骤。

根据南x坐标的递增顺序对南北对进行排序。
如果两个南x坐标相同，则根据北x坐标的递增顺序进行排序。
现在找到子序列北x坐标的。
需要注意的一点是，在递增的子序列中，一个值可以更大，也可以等于它之前的值。

我们还可以根据北x坐标进行排序，并在南x坐标上找到LIS。

CPP

                         // C++ implementation of building bridges                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // north-south coordinates                       
                         // of each City Pair                       
                         struct                                     CityPairs                       
                         {                       
                                                 int                                     north, south;                       
                         };                       
           
                         // comparison function to sort                       
                         // the given set of CityPairs                       
                         bool                                     compare(                                     struct                                     CityPairs a,                                     struct                                     CityPairs b)                       
                         {                       
                                                 if                                     (a.south == b.south)                       
                                                 return                                     a.north < b.north;                       
                                                 return                                     a.south < b.south;                       
                         }                       
           
                         // function to find the maximum number                       
                         // of bridges that can be built                       
                         int                                     maxBridges(                                     struct                                     CityPairs values[],                                     int                                     n)                       
                         {                       
                                                 int                                     lis[n];                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 lis[i] = 1;                       
                                   
                                                 sort(values, values+n, compare);                       
                                   
                                                 // logic of longest increasing subsequence                       
                                                 // applied on the northern coordinates                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 for                                     (                                     int                                     j=0; j<i; j++)                       
                                                 if                                     (values[i].north >= values[j].north                       
                                                 && lis[i] < 1 + lis[j])                       
                                                 lis[i] = 1 + lis[j];                       
                                   
                                   
                                                 int                                     max = lis[0];                       
                                                 for                                     (                                     int                                     i=1; i<n; i++)                       
                                                 if                                     (max < lis[i])                       
                                                 max = lis[i];                       
                                   
                                                 // required number of bridges                       
                                                 // that can be built                       
                                                 return                                     max;                       
                         }                       
           
                         // Driver program to test above                       
                         int                                     main()                       
                         {                       
                                                 struct                                     CityPairs values[] = {{6, 2}, {4, 3}, {2, 6}, {1, 5}};                       
                                                 int                                     n = 4;                       
                                                 cout <<                                     "Maximum number of bridges = "                       
                                                 << maxBridges(values, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program for maximizing the no. of bridges                       
                         // such that none of them cross each other                       
           
                         import                                     java.util.*;                       
           
                         class                                     CityPairs                                     // Create user-defined class                       
                         {                       
                                                 int                                     north, south;                       
                                                 CityPairs(                                     int                                     north,                                     int                                     south)                                     // Constructor                       
                                                 {                       
                                                 this                                     .north = north;                       
                                                 this                                     .south = south;                       
                                                 }                       
                         }                       
                         // Use Comparator for manual sorting                       
                         class                                     MyCmp                                     implements                                     Comparator<CityPairs>                       
                         {                       
                                                 public                                     int                                     compare(CityPairs cp1, CityPairs cp2)                       
                                                 {                       
                                                 // If 2 cities have same north coordinates                       
                                                 // then sort them in increasing order                       
                                                 // according to south coordinates.                       
                                                 if                                     (cp1.north == cp2.north)                       
                                                 return                                     cp1.south - cp2.south;                       
           
                                                 // Sort in increasing order of                       
                                                 // north coordinates.                       
                                                 return                                     cp1.north - cp2.north;                       
                                                 }                       
                         }                       
                         public                                     class                                     BuildingBridges {                       
                                                 // function to find the max. number of bridges                       
                                                 // that can be built                       
                                                 public                                     static                                     int                                     maxBridges(CityPairs[] pairs,                                     int                                     n)                       
                                                 {                       
                                                 int                                     [] LIS =                                     new                                     int                                     [n];                       
                                                 // By default single city has LIS = 1.                       
                                                 Arrays.fill(LIS,                                     1                                     );                       
           
                                                 Arrays.sort(pairs,                                     new                                     MyCmp());                                     // Sorting->                       
                                                 // calling                       
                                                 // our self made comparator                       
           
                                                 // Logic for Longest increasing subsequence                       
                                                 // applied on south coordinates.                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++) {                       
                                                 for                                     (                                     int                                     j =                                     0                                     ; j < i; j++) {                       
                                                 if                                     (pairs[i].south >= pairs[j].south)                       
                                                 LIS[i] = Math.max(LIS[i], LIS[j] +                                     1                                     );                       
                                                 }                       
                                                 }                       
                                                 int                                     max = LIS[                                     0                                     ];                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++) {                       
                                                 max = Math.max(max, LIS[i]);                       
                                                 }                       
           
                                                 // Return the max number of bridges that can be                       
                                                 // built.                       
                                                 return                                     max;                       
                                                 }                       
           
                                                 // Driver Program to test above                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     4                                     ;                       
                                                 CityPairs[] pairs =                                     new                                     CityPairs[n];                       
                                                 pairs[                                     0                                     ] =                                     new                                     CityPairs(                                     6                                     ,                                     2                                     );                       
                                                 pairs[                                     1                                     ] =                                     new                                     CityPairs(                                     4                                     ,                                     3                                     );                       
                                                 pairs[                                     2                                     ] =                                     new                                     CityPairs(                                     2                                     ,                                     6                                     );                       
                                                 pairs[                                     3                                     ] =                                     new                                     CityPairs(                                     1                                     ,                                     5                                     );                       
                                                 System.out.println(                                     "Maximum number of bridges = "                       
                                                 + maxBridges(pairs, n));                       
                                                 }                       
                         }                       

输出：

Maximum number of bridges = 2

时间复杂度：O（n） ^2. )

方法2（LIS中的优化）

注—— 这是最长递增子序列（LIS）的变化/应用。

第一步首先让一侧在桥的北面，另一侧在桥的南面。

第2步让我们从北边开始，根据元素的位置对元素进行排序。

步骤3：根据北侧进行排序，因此它正在增加，如果我们在南侧应用LIS，那么我们将能够获得不重叠的桥梁。

注—— 最长的递增子序列可以使用耐心排序在O（NlogN）中完成。

主要的优化在于最小的元素在LIS中有更高的贡献率。

输入：6 4 2 1

2 3 6 5

第1步-在桥的北面位置对输入进行排序。

1 2 4 6

5 6 3 2

步骤2：在南岸5 6 3 2处应用LIS

在LIS的优化中，如果我们发现一个元素比当前元素小，那么我们将替换当前元素，停止当前流，并从新的较小元素开始。如果我们找到比当前元素更大的元素，我们就会增加答案。

我们发现3比6小

我们发现2比3小

2（答案=1）

最终答案=2

C++

                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     non_overlapping_bridges(vector<pair<                                     int                                     ,                                     int                                     >> &temp,                                     int                                     n)                       
                         {                       
                                                 //Step - 1 Sort the north side.                       
                                                 sort(temp.begin(),temp.end());                       
                                                 // Create the Dp array to store the flow of non overlapping bridges.                       
                                                 // ans-->Store the final max number of non-overlapping bridges.                       
                                                 vector<                                     int                                     > dp(n+1,INT_MAX);                       
                                                 int                                     ans=0;                       
                                                 for                                     (                                     int                                     i=0;i<n;i++)                       
                                                 {                       
                                                 int                                     idx=lower_bound(dp.begin(),dp.end(),temp[i].second)-dp.begin();                       
                                                 dp[idx]=temp[i].second;                       
                                                 ans=max(ans,idx+1);                       
                                                 }                       
                                                 return                                     ans;                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     n=4;                       
                                                 vector<pair<                                     int                                     ,                                     int                                     >> temp;                       
                                                 temp.push_back(make_pair(6,2));                       
                                                 temp.push_back(make_pair(4,3));                       
                                                 temp.push_back(make_pair(2,6));                       
                                                 temp.push_back(make_pair(1,5));                       
                                   
                                                 cout<<non_overlapping_bridges(temp,n)<<endl;                       
                                                 return                                     0;                       
                         }                       

产出——2

时间复杂度–O（NlogN）

空间复杂性——O（N）

问题参考： https://www.geeksforgeeks.org/dynamic-programming-set-14-variations-of-lis/ 解决方案参考： https://www.youtube.com/watch?v=w6tSmS86C4w 本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章