hdoj1087 (DP--LIS)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1087

思路：这题很简单了，纯LIS的解法，没有一点变形，由于数据小，使用O(n^2)LIS解法就足够了，另外由于长度最长的上升子序列不一定有最大的score，故LIS的O(nlogn)最优算法不能使用，关于LIS可以参考我的另一篇随笔：https://www.cnblogs.com/FrankChen831X/p/10384238.html。

AC代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,res,a[1005],f[1005];
 5 
 6 int main(){
 7     while(scanf("%d",&n)!=EOF&&n){
 8         res=0;
 9         for(int i=0;i<n;i++)
10             scanf("%d",&a[i]),f[i]=a[i];
11         for(int i=0;i<n;i++){
12             for(int j=0;j<i;j++)
13                 if(a[j]<a[i])
14                     f[i]=max(f[i],f[j]+a[i]);
15             if(f[i]>res) res=f[i];
16         }
17         printf("%d
",res);
18     }
19     return 0;
20 }