本文共 869 字,大约阅读时间需要 2 分钟。
给出一个实数轴,上面散布着n个点,他们是m种,问最少挪多少步能将数轴上的点分成1~m的种类顺序排列的m块。
#include#include #include #include #define MAX 5007using namespace std;int n,m,s[MAX],dp[MAX];double x;int main ( ){ while ( ~scanf ( "%d%d" , &n , &m ) ) { for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d %lf" , &s[i] , &x ); s[++n] = m+1; for ( int i = 1 ; i <= n ; i++ ) { dp[i] = 0; for ( int j = 1; j < i ; j++ ) if ( s[i] >= s[j] ) dp[i] = max ( dp[i] , dp[j] ); dp[i]++; } printf ( "%d\n" , n-dp[n] ); }}
转载地址:http://yqvjn.baihongyu.com/