LIS HDOJ 1257 最少拦截系统

题目传送门

题意：中文题面

分析：LIS模板题：n - 最长下降子序列 -> 最长上升子序列　　贪心做法以后再补:)

代码：

#include 
#include 
#include 
#include 
#include 
using namespace std;const int MAXN = 1e4 + 10;
const int INF = 0x3f3f3f3f;
int a[MAXN];
int dp[MAXN];
int n;void LIS() {memset (dp, 0, sizeof (dp));int ans = 0;for (int i=1; i<=n; ++i)    {dp[i] = 1;for (int j=1; j a[j] && dp[i] < dp[j] + 1)    {dp[i] = dp[j] + 1;}}ans = max (ans, dp[i]);}printf ("%d\n", ans);
}int main(void)  {while (scanf ("%d", &n) == 1)   {for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);LIS ();}return 0;
}

转载于:https://www.cnblogs.com/Running-Time/p/4479109.html