HDU1087上升子序列的最大和

 解法一

此题是一个简单的动态规划问题，用dp[i]记做最后一步经过第i个数所得到的最大sum值,则结果=max(dp[i]),i=1,…n.考虑dp[i]的前一步会经过那里？假设dp[i]的前一步经过第j个数，则子问题dp[j]满足最优子结构。dp[i]=a[i]+max(dp[j]) .(a[j]<a[i]);

/*---dp[i]表示最后一步经过第i个数
----转移方程dp[i]=a[i]+max(dp[j])(a[j]<a[i],j<i)
*/
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1000 + 10;
LL dp[MAXN];
int a[MAXN];
int main(){
int n, i, j;
while (scanf("%d", &n) && n){
for (i = 1; i <=n; i++)
scanf("%d", &a[i]);
memset(dp,0, sizeof(dp));
dp[1] = a[1];
LL ans =dp[1];
for (i = 2; i <= n; i++){
dp[i] = a[i];
for (j = 1; j < i; j++){
if (a[j]<a[i])
  dp[i] = max(dp[i], dp[j]+a[i]);
}
ans = max(ans, dp[i]);
}
printf("%I64d\n", ans);
}
return 0;
}

　　解法二  转化为GAD模型

考虑若i<j，同时选择a[i]和a[j]的合法条件是a[i]<a[j].于是在数组中寻找满足i<j且a[i]<a[j]，将i向j连接一条有向边。用dp[i]表示从i出发可以得到的最大和，则有：

dp[i]=a[i]+max(dp[j]) .j是i的邻接点。采用记忆化搜索来求解。

/*---DAG模型求解
----若序列中a[i]<a[j](i<j)则从i到j连接一条有向边
*/
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 1000 + 10;
LL dp[MAXN];
int a[MAXN];
vector<int>vec[MAXN];
//记忆化搜索
LL dfs(int i){
LL &ans = dp[i];
if (ans >= 0)
return ans;
ans = 0;
for (int j = 0; j < (int)vec[i].size(); j++){
ans = max(ans,dfs(vec[i][j]));
}
return ans=ans + a[i];
}
int main(){
int n, i,j;
while (scanf("%d", &n) && n){
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
for (i = 0; i < n; i++){
vec[i].clear();
for (j = i + 1; j < n; j++){
if (a[j]>a[i])
vec[i].push_back(j);  //i到j有向边
}
}
LL ans = 0;
memset(dp, -1, sizeof(dp));
for (i = 0; i < n; i++){
if (dp[i]<0)
dp[i] = dfs(i);
ans = max(ans, dp[i]);
}
printf("%I64d\n", ans);
}
return 0;
}