http://acm.hdu.edu.cn/showproblem.php?pid=1257
一开始的时候还用了单调栈维护，toNext[i] 表示第i个往右边，第一个比它小的数。
我还以为一路这样弄下去就搞定了。
但是有数据卡我了。
6 5 6 5 4 3 2 1 5 4 3 2 1
这样其实只需要两个。但是我的做法会输出3个。。
正解是一个简单的dp
dp[i]表示第i个导弹拦截的最小高度。
然后用一个ans记录一共用了多少枚导弹
每有一个新的值，就优先找一枚合法的导弹放进去就行了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 30000 + 20; int dp[maxn]; int n; void work() { // memset(dp, 0x3f, sizeof dp); int ans = 0; for (int i = 1; i <= n; ++i) { int a; scanf("%d", &a); int j; for (j = 1; j <= ans; ++j) { if (dp[j] >= a) { dp[j] = a; break; } } if (j == ans + 1) dp[++ans] = a; } cout << ans << endl; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif while (scanf("%d", &n) != EOF) work(); return 0; }
这题还有另外一个做法。
采用逆向思维，现在它是要分成若干个最长不升子序列。
那么相反的就是最长上升子序列。输出长度即可。
为什么呢？
因为最长上升子序列，都是选取一些尽可能小的点组合成的，而这些点，刚好就是没得下降的点啦。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 30000 + 20; int dp[maxn]; int a[maxn]; int n; void work() { int lendp = 0; for (int i = 1; i <= n; ++i) cin >> a[i]; dp[++lendp] = a[1]; for (int i = 2; i <= n; ++i) { if (a[i] > dp[lendp]) { dp[++lendp] = a[i]; } else { int pos = lower_bound(dp + 1, dp + 1 + lendp, a[i]) - dp; dp[pos] = a[i]; } } cout << lendp << endl; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif while (cin >> n) work(); return 0; }