hdu1087 参考答案

   1 /*
   2 hdu 1087 DP：严格递增子列最大和
   3 ymc 2008/09/22
   4 题目大意：
   5 给定n个数的一个数列a1,a2,...an
   6 求a的一个严格递增子列，是的子列的和最大。输出子列的最大和。
   7 分析与解题思路：
   8 ans[k]为以a[k]结尾的严格递增子列的最大值。
   9 则ans[k]=max{ans[i]+a[k]},满足1<=i<k,a[i]<a[k]。
  10 */
  11 #include <iostream>
  12 using namespace std;
  13 const int N=1005;
  14 int a[N];
  15 int ans[N];
  16 int n;
  17 void DP()
  18 {
  19     int Max=0;
  20     memset(ans,0,sizeof(ans));
  21     for(int k=1;k<=n;k++)
  22     {
  23         for(int i=0;i<k;i++)
  24         {
  25             if(a[i]<a[k]&&ans[i]+a[k]>ans[k])
  26             {
  27                 ans[k]=ans[i]+a[k];
  28                 if(ans[k]>Max)
  29                     Max=ans[k];
  30             }
  31         }
  32     }
  33     printf("%d\n",Max);
  34 }
  35 int main()
  36 {
  37     while(scanf("%d",&n),n)
  38     {
  39         for(int i=1;i<=n;i++)
  40             scanf("%d",&a[i]);
  41         DP();
  42     }
  43 }