36
对于最长上升子序列，用递归的效率可能比较低，提交的时候爆时间了，用数组可以AC。 #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<iostream> #include<algorithm> #include<queue> #include<stack> //#define DEBUG using namespace std; int a[7005]; int n,best; stack<int>s; void dfs(int i); int main() { #ifdef DEBUG freopen("Text.txt", "r", stdin); #endif // DEBUG while (cin >> n) { int i, j; for (i = 0; i < n; i++) cin >> a[i]; best = 0; dfs(0); cout << best << endl; } return 0; } void dfs(int i) { if (i == n) { if (s.size() > best) best = s.size(); return ; } if (s.empty() || a[i] > s.top()) { s.push(a[i]); dfs(i + 1); s.pop(); } if (s.size() + n - i - 1 > best) dfs(i + 1); } 下面是用数组实现的代码： #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<iostream> #include<algorithm> #include<queue> #include<stack> //#define DEBUG using namespace std; int a[7005],d[7005]; int n,best; int main() { #ifdef DEBUG freopen("Text.txt", "r", stdin); #endif // DEBUG while (cin >> n) { int i, j; for (i = 1; i <= n; i++) cin >> a[i]; best = 0; d[0] = 1; for (i = 1; i <= n; i++) { d[i] = 1; for (j = 1; j <= i; j++) { if (a[j]<a[i] && d[j] + 1>d[i]) d[i] = d[j] + 1; } } for (i = 1; i <= n; i++) if (d[i] > best) best = d[i]; cout << best << endl; } return 0; }