中级天翼
谁有线性DP的讲义？
我忘了！！！
中级天翼
算法初级班第三阶段第三讲（最长不下降子序列）
最长不下降子序列
相关概念
- 序列
若干个数字排成1行称为一个序列。 - 子序列
从序列中抽取若干个数字，并按照原来的顺序排列，称为子序列。 - 不下降子序列
在子序列的基础上，要求序列中的数字大小是不下降的，这样的子序列称为不下降子序列。 - 最长不下降子序列
在所有不下降子序列中，数字个数最多的序列，称为最长不下降子序列。
例如：13 7 9 16 38 24
（1）7 9 16 24
（2）7 9 16 38
都是最长不下降子序列，长度为4
问题描述
求出一个序列最长的不下降子序列
状态
f[i]表示序列中到第i个数为止，且必取第i个数的最长不下降序列的长度。
边界
f[i]=1
状态转移方程：
f[i]=max(f[i],f[j]+1)
满足条件1<=j<=i-1且a[j]<=a[i]
目标
max(f[i]) 1<=i<=n
伪代码
ans=1
f[1]=1
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=i-1;j>=1;j--){
if(w[i]<=w[j]&&f[j]+1>f[i])
f[i]=f[j]+1;
}
ans=max(ans,f[i]);
}
课堂题：3912 导弹拦截
#include<iostream> using namespace std; int a[1005],f[1010]; int main(){ int n=0,ans=1; while(cin>>a[++n]); n--; for(int i=1;i<=n;i++){ f[i]=1; for(int j=1;j<=i-1;j++) if(a[i]<=a[j]) f[i]=max(f[j]+1,f[i]); ans=max(ans,f[i]); } cout<<ans; return 0; }
课堂题：3142 仪仗队
#include<iostream> using namespace std; int a[105],f1[105],f2[105]; int main(){ int n,ans=0; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ f1[i]=1; for(int j=1;j<i;j++) if(a[i]>a[j]) f1[i]=max(f1[j]+1,f1[i]); } for(int i=n;i>=1;i--){ f2[i]=1; for(int j=n;j>i;j--) if(a[i]>a[j]) f2[i]=max(f2[j]+1,f2[i]); } for(int i=1;i<=n;i++) ans=max(ans,f1[i]+f2[i]-1); cout<<n-ans; return 0; }
课堂题：3920 序列探秘
#include<iostream> using namespace std; int a[100005],b[200005],f[100005]; int main(){ int n,k,ans=0; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ f[i]=1; if(a[i]-k+100000>=0&&a[i]-k+100000<=200000) f[i]=max(f[b[a[i]-k+100000]]+1,f[i]); ans=max(f[i],ans); b[a[i]+100000]=i; } cout<<ans; return 0; }
算法初级班第三阶段第四讲（简单线性DP）
算法初级班第三阶段第四讲（简单线性DP）
本节课主要探讨的问题是跳一跳类的问题：
对于这类问题，还是要抓住动态规划的本质，实际上是一个复杂的递推式，可以由前面的状态推出当前状态。
动态规划的最优化原理：
子问题的局部最优解导致整个问题的全局最优。
动态规划的无后效性原则
某阶段的状态一旦确定，不会受前后状态影响，当前状态是此前历史的一个完整的总结。
在做这类问题时，可以先讨论题目样例，去演化递推式，然后再想具体代码。
1389 自行车比赛
状态，f[i] 骑行i公里，所花的最小费用
目标，f[n]
在10公里以内时
可以通过递推的方式得到当前状态;
在10公里之外时，比如11公里，可以由f[10]和f[1]得到,当然也可以再考虑一次f[10]+a[1]，但在算f[1]时，f[1]的值就是a[1]
此时发现可以在10公里的基础上去递推得到
（20公里以外以此类推）
因此,状态转移方程：
f[i]=max(f[i],f[i-j]+f[i]);
具体代码：
#include<iostream> using namespace std; int w[105],f[105]; int main(){ int n; cin>>n; for(int i=1;i<=10;i++) cin>>w[i]; for(int i=1;i<=n;i++){ if(i<=10) f[i]=w[i]; else f[i]=0x3f3f3f3f; for(int j=1;j<=i;j++){ f[i]=min(f[i],f[i-j]+f[j]); } } cout<<f[n]; return 0; }
3228 机器人捡硬币
这道题可以看成上一道题的进化版，并且略有不同
状态：f[i]表示跳到第i个格子所能获得的最大硬币和
目标：由于本道题中有可能跳过终点，所以要讨论
f[n]–f[n+q-1]这些状态中的最大值
状态转移方程：
f[i]=max(f[i],f[i-j]+a[i]);
这里是从第i-j个格子上跳到第i个格子上，而第i个格子上的硬币是a[i]，注意和上题的区别。
代码：
#include<iostream> #include<cstring> using namespace std; int a[200205],f[200205],ans; int main(){ int n,p,q; cin>>n>>p>>q; for(int i=0;i<=n;i++) cin>>a[i]; for(int i=p;i<n+q;i++){ f[i]=a[i]; for(int j=p;j<=min(i,q);j++){ f[i]=max(f[i],f[i-j]+a[i]); } } for(int i=n;i<n+q;i++) ans=max(ans,f[i]); cout<<ans; return 0; }
另一种写法：
边界：初始化负无穷
memset(f,-0x3f,sizeof(f));
#include<iostream> #include<cstring> using namespace std; int a[200205],f[200205]; int main(){ int n,p,q,ans=0; cin>>n>>p>>q; for(int i=0;i<=n;i++) cin>>a[i]; memset(f,-0x3f,sizeof(f));//初始化负无穷，因为一开始1--p-1这些位置是跳不到的，防止从这些格子跳过来 f[0]=0;//起点可以跳，且金币就是0 //不加等于号 是因为如果要跳到n+q这个位置，是从n这个位置跳的，已经到终点了。 for(int i=p;i<n+q;i++){ for(int j=p;j<=min(i,q);j++){ if(i>=j) f[i]=max(f[i],f[i-j]+a[i]); //从i-j个格子跳到第i个格子上 } } for(int i=n;i<n+q;i++) ans=max(ans,f[i]); cout<<ans; return 0; }
算法初级班第三阶段第六讲（最长公共子序列）
最长公共子序列
一、问题描述
给定两个长度为N和M的序列A和B，求既是A的子序列又是B的子序列的最长长度是多少。那么这个最长的子序列被称为最长公共子序列（LCS）
注：有关子序列的问题可以回顾第三讲，最长不下降子序列
假设现在要求A={A1,A2,…,An}和B={B1,B2,…Bn}这两个序列的最长公共子序列长度。
状态 f[i][j]
表示序列A1~ Ai和序列B1~ Bj的最长公共子序列的长度
边界
f[i][0]=f[0][j]=0
即任何序列和空序列都没有公共子序列
目标
f[n][m]
状态转移方程
if(a[i]==b[j]) f[i][j] = f[i-1][j-1]+1; else f[i][j] = max(f[i-1][j], f[i][j-1]);
二、课堂题代码
1527 最长公共字符串
#include<iostream> #include<string> using namespace std; int f[1005][1005]; int main(){ string a,b; getline(cin,a); getline(cin,b); int n=a.length(),m=b.length(); a=" "+a,b=" "+b; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); } } cout<<f[n][m]; return 0; }
高级天翼
我还没学到，可见你已经是一位大佬了，【膜拜大佬】【叩头】
新手天翼
蒻狗一个 没学到
中级光能
- 序列
若干个数字排成1行称为一个序列。 - 子序列
从序列中抽取若干个数字，并按照原来的顺序排列，称为子序列。 - 不下降子序列
在子序列的基础上，要求序列中的数字大小是不下降的，这样的子序列称为不下降子序列。 - 最长不下降子序列
在所有不下降子序列中，数字个数最多的序列，称为最长不下降子序列。
曹砚青在2020-07-11 10:55:33追加了内容
PS:
这根红线是怎么回事？？？
初级光能
序列
若干个数字排成1行称为一个序列。
子序列
从序列中抽取若干个数字，并按照原来的顺序排列，称为子序列。
不下降子序列
在子序列的基础上，要求序列中的数字大小是不下降的，这样的子序列称为不下降子序列。
最长不下降子序列
在所有不下降子序列中，数字个数最多的序列，称为最长不下降子序列。
例如：13 7 9 16 38 24
（1）7 9 16 24
（2）7 9 16 38
都是最长不下降子序列，长度为4
问题描述
求出一个序列最长的不下降子序列
状态
f[i]表示序列中到第i个数为止，且必取第i个数的最长不下降序列的长度。
边界
f[i]=1
状态转移方程：
f[i]=max(f[i],f[j]+1)
满足条件1<=j<=i-1且a[j]<=a[i]
目标
max(f[i]) 1<=i<=n
