文章目录
- 数字三角形
- 思路
- 代码
- 最长上升子序列1
- 思路
- 代码
- 最长公共子序列
- 思路
- 代码
其实和背包一样,都不固定,这种类型的题每一道题都需要自己从之前的经验中去摸索。
数字三角形
题目链接
思路
只能从左上或者右上走过来,用一个二维数组,记录到大最后一行的最大值,再进行比较
(后续可能再加几道题)
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,INF = 1e9;
int n;
int a[N][N],f[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;i++) for (int j = 0;j <= i + 1;j++)//i要多加1,虽然最右边的右上角没有数,但是下面的方程是包括的、又因为赋值为负无穷,,所以对结果无影响f[i][j] = -INF;//把起初每个值赋为负无穷f[1][1] = a[1][1];for (int i = 2;i <= n;i++)for (int j = 1;j <= i;j++) f[i][j] = max (f[i - 1][j - 1],f[i - 1][j]) + a[i][j];int res = -INF;for (int i = 1;i <= n;i++) res = max (res,f[n][i]);//比较完之后,最大值在最后一行的某一个cout << res << endl;return 0;
}
最长上升子序列1
题目链接
思路
数据比较小,直接比较比当前小的有几个然后进行继承
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,a[N],f[N];
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++)if(a[j]<a[i])//比当前i小的f[i]=max(f[i],f[j]+1);//比较之后继承}int res=0;for(int i=1;i<=n;i++)res=max(res,f[i]);cout<<res<<'\n';return 0;
}
最长公共子序列
题目链接
思路
思路就是两个字符串慢慢比对,根据上图的注释
代码
#include<iostream>
#include<algorithm>using namespace std;
const int N=1111;
int m,n,f[N][N];
char a[N],b[N];
int main()
{cin>>n>>m;cin>>a+1>>b+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=max(f[i-1][j],f[i][j-1]);//图中中间的两种if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);//如果是图中的最后一种情况,最后一个字母必须相等} cout<<f[n][m]<<'\n';return 0;
}