建设网站平台滴滴车,怎么自己开公司,申请域名需要多久,wordpress 主机本专题主要是介绍几个比较经典的题目#xff1a; 假设我们令f[i]为前i个的最长不下降子序列#xff0c;我们会发现难以转移方程很难写#xff08;因为我们不知道最后一个数#xff09;。
于是#xff0c;我们令f[i]为以i结尾的最长不下降子序列#xff0c;这样子我们就可…本专题主要是介绍几个比较经典的题目 假设我们令f[i]为前i个的最长不下降子序列我们会发现难以转移方程很难写因为我们不知道最后一个数。
于是我们令f[i]为以i结尾的最长不下降子序列这样子我们就可以得出
f[i]max{f[j]1}(a[j]a[i]ji)
f[i]1;
复杂度为n^2;用单调队列维护可nlogn;
下面给出用递归for循环代码
#includebits/stdc.h
using namespace std;
int n,a[100000],dp[100000];
dequeint q;
int main(){cinn;for(int i1;in;i) scanf(%d,a[i]);dp[1]1;for(int i2;in;i){for(int j1;ji;j){if(a[j]a[i]) dp[i]max(dp[i],dp[j]1);}}int ans0;for(int i1;in;i) ansmax(ans,dp[i]);coutans;
}
下面是用记忆化搜索实现
#includebits/stdc.h
using namespace std;
int n,a[100000],dp[100000];
dequeint q;
int f(int x){if(dp[x]!0) return dp[x];for(int i1;ix-1;i){if(a[i]a[x]) dp[x]max(dp[x],f(i)1);}return dp[x];
}
int main(){cinn;int ans0;for(int i1;in;i) scanf(%d,a[i]);dp[1]1;for(int i1;in;i){ansmax(ans,f(i));}coutans;}
接题 我们设f[i][j]表示从i,j滑下的最长路径易得
f[i][j]max{f[i-1][j]1,f[i1][j]1,f[i][j1]1,f[i][j-1]1}(a[i-1][j]a[i][j],a[i1][j]a[i][j],a[i][j-1]a[i][j],a[i][j1]a[i][j])
在实现上for循环不知道某先f[i][j]我们需要按从低到高的顺序求比较麻烦。
于是我们用记忆化搜索。
下面是AC代码
#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
#define int long long
int a[105][105],r,c,ans,dp[105][105];
int f(int i,int j){if(i0||j0||ir||jc) return 0;if(dp[i][j]!0) return dp[i][j];if(a[i-1][j]a[i][j]) dp[i][j]max(dp[i][j],f(i-1,j)1);if(a[i1][j]a[i][j]) dp[i][j]max(dp[i][j],f(i1,j)1);if(a[i][j-1]a[i][j]) dp[i][j]max(dp[i][j],f(i,j-1)1);if(a[i][j1]a[i][j]) dp[i][j]max(dp[i][j],f(i,j1)1);if(dp[i][j]0) return dp[i][j]1;else return dp[i][j];
}
signed main(){cinrc;for(int i1;ir;i){for(int j1;jc;j){scanf(%d,a[i][j]);}}for(int i1;ir;i){for(int j1;jr;j){ansmax(ans,f(i,j));}}coutans;
}
