hdu 1087(最大递增子序列）

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

一开始我把题目理解错了，还以为是必须连续的，orz。。。。

思路：dp[i]表示第i个位置是的最大值，那么状态转移方程即为:dp[i]=dp[i-1]+num[i](num[i]>num[j],i>j);

View Code

 1 #include<iostream>
 2 const int N=1100;
 3 using namespace std;
 4 int dp[N],num[N];
 5 
 6 int main(){
 7     int n;
 8     while(scanf("%d",&n)!=EOF&&n){
 9         for(int i=0;i<n;i++){
10             scanf("%d",&num[i]);
11         }
12         dp[0]=num[0];
13         int ans=0;
14         for(int i=1;i<n;i++){
15             ans=0;
16             for(int j=0;j<i;j++){
17                 if(num[j]<num[i]&&dp[j]>ans){
18                     ans=dp[j];
19                 }
20             }
21             dp[i]=ans+num[i];
22         }
23         ans=0;
24         for(int i=0;i<n;i++){
25             ans=max(dp[i],ans);
26         }
27         printf("%d\n",ans);
28     }
29     return 0;
30 }