q1:数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
? ? ? ? 7
? ? ? 3 ? 8
? ? 8 ? 1 ? 0
? 2 ? 7 ? 4 ? 4
4 ? 5 ? 2 ? 6 ? 5
输入格式
第一行包含整数 nn，表示数字三角形的层数。
接下来 nn 行，每行包含若干整数，其中第 ii 行表示数字三角形第 ii 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤5001≤n≤500,
?10000≤三角形中的整数≤10000?10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0?
2 7 4 4
4 5 2 6 5
输出样例：
30
线性dp
?1.初始化f[i,j]时，将该点的上左，上右都初始化为-1e9,避免处理边界
?ac代码
#include <iostream>
#include <cstring>
#include <algorithm>
?
using namespace std;
int n;
const int N = 510,M=1e9;
int a[N][N];
int dp[N][N];
int main()
{
? ? cin>>n;
? ? for(int i=1;i<=n;i++)
? ? {
? ? ? ? for(int j=1;j<=i;j++)
? ? ? ? {
? ? ? ? ? ? cin>>a[i][j];
? ? ? ? }
? ? }
? ? for(int i=0;i<=n+1;i++)
? ? {
? ? ? ? for(int j=0;j<=i+1;j++)
? ? ? ? {
? ? ? ? ? ? dp[i][j]=-M;
? ? ? ? }
? ? }
? ? dp[1][1]=a[1][1];
? ? for(int i=2;i<=n;i++)
? ? {
? ? ? ? for(int j=1;j<=i;j++)
? ? ? ? {
? ? ? ? ? ? dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i-1][j]+a[i][j]);
? ? ? ? }
? ? }
? ? int m=-M;
? ? for(int i=1;i<=n;i++)
? ? {
? ? ? ? m=max(dp[n][i],m);
? ? }
? ? cout<<m;
? ? return 0;
}
q2:最长上升子序列??????
给定一个长度为?N?的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数?N。
第二行包含?N?个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤10001≤N≤1000，
?109≤数列中的数≤109?109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
?
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N=1111,M=1e9;
int a[N],f[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
f[1]=1;
for(int i=1;i<=n;i++)
{
f[i]=1;//f[i]最小为1，表示a[i]比前面的任何一个数都小
for(int j=1;j<=i;j++)
{
if(a[i]>a[j])
f[i]=max(f[i],f[j]+1);
}
}
sort(f+1,f+1+n);
cout<<f[n];
return 0;
}最长上升子序列二的数据范围为1e5，如果用上面的方法，时间复杂度为n^2,会超时?
q3：?最长上升子序列 II
给定一个长度为?N?的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数?N。
第二行包含?N?个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000001≤N≤100000，
?109≤数列中的数≤109?109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4观察得：
其存在一个性质，即，长度为i的最长上升子序列的结尾的数一定大于长度为i-1的最长上升子序列的结尾的值
q[1]=-2*M;
因为每个数最小为-1e9，保证最长上升子序列的最小长度为1二分来寻找比第i个数小的最大的数?
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N=1e5+10,M=1e9;
int a[N];
int q[N];//q[i]表示长度为i的序列的结尾的最小的数
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int len=0;
q[1]=-2*M;
for(int i=1;i<=n;i++)
{
int l=0,r=len;
while(l<r)
{
int mid=l+r+1>>1;
if(q[mid]<a[i]) l=mid;
else r=mid-1;
}
len=max(len,r+1);
q[r+1]=a[i];
}
cout<<len;
return 0;
}