浅说线性DP（下）
声明
最近博主身体不适，更新较慢，请大家体谅体谅
最大上升子序列
【题目描述】
一个数的序列
你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。
【输入】
输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。
【输出】
最大上升子序列和。
如果前面的最长上升子序列那道题理解清楚了，那么该题做起来就会发现本质上和前一道题是一样的。该题的决策对象和阶段都和前一道题一样，只是状态变为dp[i]表示以第i个数作为结尾的最大上升子序列的长度。
决策：这里要求子序列之和最大，对于每一个位置的数，只能从前面的比当前值小的数转移过来，要求序列之和最大，那么这个序列前面选择的数之和要最大，那么我们需要从前面可以选择的点中序列和最大的点转移过来。
我们设dp[i]表示以i结尾的最大子序列之和，那么我们就可以很轻松的得到一下内容
d p [ i ] = m a x ( d p [ i ] , d p [ j ] + a [ i ] ) j ∈ [ 1 , i − 1 ] dp[i]=max(dp[i],dp[j]+a[i]) j\in[1,i-1] dp[i]=max(dp[i],dp[j]+a[i])j∈[1,i−1]
所以就有以下ACcode
#include
using namespace std;
int a[10010],dp[10010],ans=INT_MIN;
int main(){
int n;
cin>>n;
for (int i=1;i
cin>a[i];
dp[i]=a[i];
}
for (int i=1;i
for (int j=1;j
if (a[j]
dp[i]=max(dp[i],dp[j]+a[i]);
}
}
ans=max(ans,dp[i]);
}
coutt_k(1\le i\le k)
>tk(1≤i≤k)。
你的任务是，已知所有
n
n
n 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
共二行。
第一行是一个整数
n
n
n（
2
≤
n
≤
100
2\le n\le100
2≤n≤100），表示同学的总数。
第二行有
n
n
n 个整数，用空格分隔，第
i
i
i 个整数
t
i
t_i
ti（
130
≤
t
i
≤
230
130\le t_i\le230
130≤ti≤230）是第
i
i
i 位同学的身高（厘米）。
输出格式
一个整数，最少需要几位同学出列。
样例 #1
样例输入 #1
8
186 186 150 200 160 130 197 220
样例输出 #1
4
提示
对于
50
%
50\%
50% 的数据，保证有
n
≤
20
n \le 20
n≤20。
对于全部的数据，保证有
n
≤
100
n \le 100
n≤100。
该题实际上就是前面求一个最长上升子序列，对后面求一个最长下降子序列。但是问题在于这两个序列的连接点我们不知道，没有办法直接求解出来，也就是说任意一个点都有可能作为这个连接点，所以我们需要先枚举这个连接点x，再分别对区间[1,x]求最长上升子序列，对区间[x+1,n]求最长下降子序列。这种做法的时间复杂度为O(n3),但是该题的数据范围改为n
cin>n;
for (int i=1;i
cin>a[i];
dp1[i]=1;
dp2[i]=1;
}
for (int i=1;i
for (int j=1;j
if (a[j]
dp1[i]=max(dp1[i],dp1[j]+1);
}
}
}
for (int i=n;i=1;i--){
for (int j=n;ji;j--){
if (a[i]a[j]){
dp2[i]=max(dp2[i],dp2[j]+1);
}
}
}
for (int i=n;i>=1;i--){
minn=min(n-dp1[i]-dp2[i],minn);
}
cout
string a,b;
cina>>b;
dp[0][0]=0;
for (int i=1;i
for (int j=1;j
if (a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout
string a,b;
cinab;
dp[0][0]=0;
for (int i=1;i
for (int j=1;j
if (a[i-1]==b[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
maxn=max(dp[i][j],maxn);
}
}
cout
