1 solutions
-
0
题解:
题目要求,给一行数据,要把这些数据拆成尽可能长的几个下降序列;
for(int i = 1;i <= n;++ i) { int t = 1; for(;t <= cnt;++ t) { if(a[i] <= c[t])break; } c[t] = a[i]; if(t > cnt)cnt ++; }
假设目前开辟了cnt个数列,后面遇到的数我们就要么开辟新的要么放在旧的后面;
```#include<bits/stdc++.h> typedef long long LL; using namespace std; const int N = 1e5 + 10; int n,ans,cnt; int a[N],b[N],c[N]; int main () { n = 1; while(cin >> a[n])n++; n --; for(int i = 1;i <= n;++ i) { b[i] = 1; for(int j = 1;j < i;++ j) { if(a[j] >= a[i])b[i] = max(b[i],b[j] + 1); } ans = max(ans,b[i]); } for(int i = 1;i <= n;++ i) { int t = 1; for(;t <= cnt;++ t) { if(a[i] <= c[t])break; } c[t] = a[i]; if(t > cnt)cnt ++; } cout << ans << "\n" << cnt << "\n"; return 0; }
- 1
Information
- ID
- 6865
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- 10
- Tags
- (None)
- # Submissions
- 1
- Accepted
- 1
- Uploaded By