HDU-1257-最少拦截系统
传送门
这道题是LIS，最长递增子序列。
中文题目，我就不多说啦。
dp代码思想:
模拟计算过程：
1.从第一个数开始，找一个最长的递减子序列，即第一个拦截系统X，在样例中式{389， 300， 299， 170， 158， 65},去掉这些数，序列中还剩下{207, 155}.
2.在剩下的序列中再找一个最长递减子序列，即第二个拦截系统Y，是{207， 155}
在Y中，至少有一个数a大于X中的某个数，否则a比X的所有数都小，应该在X中，所以，从每个拦截系统中拿出一个数能够成一个递增子序列，即拦截系统的数量等于这个递增子序列的长度。如果这个递增子序列不是最长的，那么可以从某个拦截系统中拿出两个数c, d，在拦截系统中c > d，c和d不是递增的，这与递增序列的要求矛盾。
我们定义状态dp[i]，表示以第i个数结尾的最长递增子序列的长度。
那么：
dp[i] = max{0, dp[j]} + 1；0 < j < i, Ai > Aj
最后的答案就是max{dp[i]}；
代码部分：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;int n;
int a[N];int LIS()
{
int ans = 1;int dp[N] = {
0};dp[1] = 1;for (int i = 2; i <= n; i++){
int maxx = 0;for (int j = 1; j < i; j++){
if (dp[j] > maxx && a[j] < a[i]){
maxx = dp[j];}}dp[i] = maxx + 1;if (dp[i] > ans){
ans = dp[i];}}return ans;
}int main()
{
while (cin >> n){
for (int i = 1; i <= n; i++){
scanf ("%d", &a[i]);}cout << LIS() << endl;}return 0;
}