进击的巨人（DP?）
巨人排队
查看题解 查看答案
题目描述
Time Limit: 1000 ms
Memory Limit: 256 mb
巨人国的小学生放假了，老师要给小朋友们排队了。可是这个老师有强迫症，一定要路队上的小朋友按照身高从高到矮排序（也就是排在前面的不能比后面的矮）。小朋友呢也很调皮，一旦老师给他排好队就不愿意动了。这个时候小朋友们一个一个的从教室里出来了，每个小朋友一出来老师就要给小朋友安排好位置。请问老师最少要给小朋友排几条路队呢？
输入输出格式
输入描述:
多组数据输入。 对于每组数据，第一行两个数n，表示小朋友总数量(1<=n<=100000) 第二行n个整数，表示小朋友身高，身高不超过30000
输出描述:
对于每组数据，输出一个整数，表示最少的路队数
输入输出样例
输入样例#:
复制
8 389 207 155 300 299 170 158 65
输出样例#:
复制
2
提示
最少要排两条路队，其中一种方案是398-207-155-65 和 300-299-170-158
题目来源
中南大学机试题
#include<bits/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(cin>>n){ for(int i = 0; i < n; i ++){ cin>>s[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; } // cout<<s[i]<<" "<<temp<<endl; if(s[i] <= temp){//加入并成为头 temp = s[i]; s[i] = -1; } } s[begin] = -1; count ++; num = 0;//统计人数 for(int i = 0; i < n; i ++){ // cout<<s[i]<<" "; if(s[i] > 0){ num ++; } } } cout<<count<<endl; } }#include<bits/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(cin>>n){ for(int i = 0; i < n; i ++){ cin>>s[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]); } } cout<<m<<endl; } }