这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
终于回到家了，万恶的期末考试也结束了，这次期末考试比较有纪念意义，因为我考到了读书15年来的最低分----《检测技术与装置》考了33分=。=
好吧，开学得去补考，废话不多说，拿水题来开刀！
注意此题要逆向思考！
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1257
标准的LIS（最长上升子序列）题目，我用的是O(n^2)的方法。
LIS算法详细讲解见：http://www.wutianqi.com/?p=1850
#include
using namespace std;
int arr[1005];
int dp[1000];
int LIS(int *arr, int n)
{
for(int i=1; i<=n; ++i)
dp[i] = 0;
int ans;
dp[1] = 1;
for(int i=2; i<=n; ++i)
{
ans = dp[i];
for(int j=1; jarr[j] && dp[j]>ans)
ans = dp[j];
}
dp[i] = ans+1;
}
ans = 0;
for(int i=1; i<=n; ++i)
{
if(dp[i] > ans)
ans = dp[i];
}
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
int n;
while(scanf("%d", &n;) != EOF)
{
for(int i=1; i<=n; ++i)
cin >> arr[i];
cout << LIS(arr, n) << endl;
}
return 0;
}