巨人排队查看题解 查看答案题目描述Time Limit: 1000 msMemory Limit: 256 mb巨人国的小学生放假了老师要给小朋友们排队了。可是这个老师有强迫症一定要路队上的小朋友按照身高从高到矮排序也就是排在前面的不能比后面的矮。小朋友呢也很调皮一旦老师给他排好队就不愿意动了。这个时候小朋友们一个一个的从教室里出来了每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友排几条路队呢输入输出格式输入描述:多组数据输入。 对于每组数据第一行两个数n表示小朋友总数量(1n100000) 第二行n个整数表示小朋友身高身高不超过30000输出描述:对于每组数据输出一个整数表示最少的路队数输入输出样例输入样例#:复制8 389 207 155 300 299 170 158 65输出样例#:复制2提示最少要排两条路队其中一种方案是398-207-155-65 和 300-299-170-158题目来源中南大学机试题#includebits/stdc.h using namespace std; #define N 1000005 int dp[N] {0}; int v[N] {0}; int t[N] {0}; int s[N] {0}; int find(int s[N], int n){ for(int i 0; i n; i ){ if(s[i] 0){ return i; } } return -1; } int main(){ int n, k; while(cinn){ for(int i 0; i n; i ){ cins[i]; } int count 0; int num n; while(num){ int begin find(s, n); int temp s[begin]; for(int i begin 1; i n; i ){ if(s[i] -1){//没人 continue; } // couts[i] tempendl; if(s[i] temp){//加入并成为头 temp s[i]; s[i] -1; } } s[begin] -1; count ; num 0;//统计人数 for(int i 0; i n; i ){ // couts[i] ; if(s[i] 0){ num ; } } } coutcountendl; } }#includebits/stdc.h using namespace std; int dp[10005]; int dp1[10005]; int dp2[10005]; int t[10005]; // 重量/耗时 int v[10005]; // 价值 int s[100005]; int pre[100005]; int main(){ int n, w; while(cinn){ for(int i 0; i n; i ){ cins[i]; dp[i] 1; } int m -1; int count 0; for(int i 0; i n; i ){ for(int j 0; j i; j ){ if(s[i] s[j]){ dp[i] max(dp[i], dp[j] 1); } m max(m, dp[i]); } } coutmendl; } }