Dp|线段覆盖（动态规划）
http://wikioi.com/problem/1214/
【Dp|线段覆盖（动态规划）】
#include
#include
#include
#include
#include
#include
#includeusing namespace std;
#define maxn 1005
int dp[ maxn ] ;
struct node
{
int left , right , value ;
}edge[ maxn ] ;
int cmp( const node a , const node b )
{
return a.right < b.right ;
}int main()
{
int n ;
scanf( "%d" , &n ) ;
{
memset( edge , 0 , sizeof( edge ) ) ;
for( int i = 1 ;
i <= n ;
++i )
{
scanf( "%d%d" , &edge[ i ].left , &edge[ i ].right ) ;
if( edge[ i ].left > edge[ i ].right )
{
int temp = edge[ i ].left ;
edge[ i ].left = edge[ i ].right ;
edge[ i ].right = temp ;
}
}
sort( edge + 1 , edge + n + 1 , cmp ) ;
edge[ 1 ].value = https://www.it610.com/article/1 ;
for( int i = 2 ;
i <= n ;
++i )
{
for( int j = 1 ;
j <= i - 1 ;
++j )
{
if( edge[ i ].left>= edge[ j ].right )
{
edge[ i ].value = https://www.it610.com/article/max( edge[ i ].value , edge[ j ].value + 1 ) ;
}
}
}int Max = 0 ;
for( int i = 1 ;
i <= n ;
++i )
{if( Max < edge[ i ].value )
Max = edge[ i ].value;
}
printf("%d\n" , Max ) ;
}
return 0 ;
}
推荐阅读
- Trie树（动态规划）
- 地图|高德地图清除指定覆盖物 自定义覆盖物样式（完整dome）
- 浅谈Go切片的值修改是否会覆盖数组的值
- 斐波那契数列如何快速计算-动态规划法
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- 动态规划|暴力递归经典问题
- 416.分割等和子集
- Java数据结构和算法-动态规划算法解决背包问题
- [Golang]力扣Leetcode—初级算法—动态规划—打家劫舍