hrbust/哈理工oj 1334 最好的心情【求最长递增子序列最大值】

hrbust/哈理工oj 1334 最好的心情【求最长递增子序列最大值】

思路：

首先用dp搞一下最长递增子序列，然后我们再对dp【】数组值进行探究。

我们知道，dp【i】表示从0-i最长递增子序列的长度，对于这样一组样例：

5

5 4 4 4 9

对应dp值为：
1 1 1 1 2

很明显 最长递增子序列的长度为2,辣么我们要怎样求出最大和呢？我们可以选择这样的方案：从后向前扫，先扫dp【i】==最长递增子序列长度的a【i】，然后找到最大值，记录这个最大值的位子，然后下一次再从这个位子向前扫，找到dp【i】==最长递增子序列长度-1的a【i】，再记录最大值，一直持续到dp【i】==1为止。然后将这些最大值加和。那么是不是这样搞一发就皆大欢喜了捏？

有这样一组样例：

4

1 9 2 3

对应dp值为：

1 2 2 3

明显这样搞我们还拉下了这样的一种情况。那么我们还需要维护一个变量pre，表示上一次扫求得的最大值。使得当前扫到的a【i】一定要小于pre才可以选择记录这个a【i】.

思路构建完毕，最后上AC代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define ll long long int
ll a[10000];
int dp[10000];
ll output;
void dfs(int tmp,int k,int pre)
{if(tmp==0)return ;int pos;ll maxn=0;for(int i=k;i>=0;i--){if(tmp==dp[i]){if(a[i]>maxn){if(pre==-1||a[i]<pre){pos=i;maxn=a[i];}}}}output+=maxn;dfs(tmp-1,pos,maxn);
}
int main()
{int n;while(~scanf("%d",&n)){if(n==0)break;memset(dp,0,sizeof(dp));for(int i=0; i<n; i++){scanf("%lld",&a[i]);}if(n==1){printf("1 %lldn",a[0]);continue;}dp[0]=1;int ans=0;for(int i=1; i<n; i++){int maxn=0;for(int j=0; j<i; j++){if(a[j]<a[i]&&dp[j]>maxn){maxn=dp[j];}}dp[i]=maxn+1;ans=max(dp[i],ans);}output=0;printf("%d",ans);dfs(ans,n-1,-1);printf(" %lldn",output);}
}