AKSZ-DP2
2024-06-23 18:07:54
发布于:广东
背包
1.字串和子序列
子序列:不连续的
字串 :连续的
2.dp记忆化搜索
方法——结尾法
- dp[i] 表示以下标 i 作为结尾的答案,ans是{dp[1]~dp[n]}的最优值
过程
$\large\textbf{遍历,用 j 下标表示}$
转移条件
$dp[i]=max(dp[i],dp[j]+1); $
多维技巧
若低维状态无法描述问题,那我们开高维
X Y ={最长公共子序列}
dp[i][j]//什么含义
前缀法 定义状态
含义例子:就表示~处理完毕的结果,.
表示序列处理完 前项,
序列 处理完前j项的最大公共子序列
if(X[i]==Y[j])dp[i][j] =dp[i-1][j-1]+1;//一定是最优的
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
正解:
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
int n;
int a[1100], f[1100], ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
f[i] = 1;
}
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
for (int i = 1; i <= n; i++)
ans = max(ans, f[i]);
cout << ans;
return 0;
}
DAG模型
有向无环图
这里空空如也
有帮助,赞一个