😽 PREFACE
🎁欢迎各位→点赞 👍 + 收藏 ⭐ + 评论 📝
📢系列专栏： 算法经典题集
🔊本专栏涉及到的知识点或者题目是算法专栏的补充与应用
💪 种一棵树最好是十年前其次是现在
DP
DP就是动态规划，其类型有以下两个特征：
重叠子问题：子问题是原大问题的小版本，计算步骤完全一样，计算大问题要多次重复计算小问题。
最优子结构：大问题的最优解包含小问题的最优解，可通过小问题去求解大问题。
0/1背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8
//未优化版本
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;//数目，背包容量
int v[N],w[N];//体积，价值
int dp[N][N];//表示所有选法集合中,只从前i个物品中选,并且总体积≤j的选法的集合,它的值是这个集合中每一个选法的最大值.
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=dp[i-1][j];//不选第i个物品的集合中的最大值
if(j>=v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);//状态转移方程
//f[i-1][j-v[i]]+w[i]:选第i个物品的集合,但是直接求不容易求所在集合的属性,这里迂回打击一下,先将第i个物品的体积减去,求剩下集合中选法的最大值.
}
}
cout<<dp[n][m]<<endl;
return 0;
}
//优化版本(后续补充~~~)
摘花生
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
输入格式
第一行是一个整数T，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数，分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据，从北向南依次描述每行花生苗的情况。每行数据有C个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据，输出一行，内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1≤T≤100,
1≤R,C≤100,
0≤M≤1000
输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16
#include <bits/stdc++.h>
using namespace std;
const int N =1010;
int row,col,q;
int a[N][N],dp[N][N];
int main()
{
cin>>q;
while(q--)
{
cin>>row>>col;
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
cout<<dp[row][col]<<endl;
}
return 0;
}最长上升子序列
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−10^9≤数列中的数≤10^9
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],dp[N],n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=1;// 找出所计算的dp[i]之中的最大值，边算边找
for(int i=1;i<=n;i++)
{
dp[i]=1;//设dp[i]默认为1，找不到前面数字小于自己的时候就为1
for(int j=1;j<i;j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);//前一个小于自己的数结尾的最大上升子序列加上自己，即+1
}
res=max(res,dp[i]);
}
cout<<res<<endl;
return 0;
}枚举
连号区间数
小明这些天一直在思考这样一个奇怪而有趣的问题：
在 1∼N 的某个排列中有多少个连号区间呢？
这里所说的连号区间的定义是：
如果区间 [L,R] 里的所有元素（即此排列的第 L 个到第 R 个元素）递增排序后能得到一个长度为 R−L+1 的“连续”数列，则称这个区间连号区间。
当 N 很小的时候，小明可以很快地算出答案，但是当 N 变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
输入格式
第一行是一个正整数 N，表示排列的规模。
第二行是 N 个不同的数字 Pi，表示这 N 个数字的某一排列。
输出格式
输出一个整数，表示不同连号区间的数目。
数据范围
1≤N≤10000,
1≤Pi≤N
输入样例1：
4
3 2 4 1
输出样例1：
7
输入样例2：
5
3 4 2 5 1
输出样例2：
9
样例解释
第一个用例中，有 7 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[2,2],[3,3],[4,4]
第二个用例中，有 9 个连号区间分别是：[1,1],[1,2],[1,3],[1,4],[1,5],[2,2],[3,3],[4,4],[5,5]
#include <bits/stdc++.h>
using namespace std;
const int N=10010,INF=1e8;
int n;
int a[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
int res=0;
for(int i=0;i<n;i++)
{
int mina=INF,maxa=-INF;
for(int j=i;j<n;j++)
{
mina=min(mina,a[j]);
maxa=max(maxa,a[j]);
if(maxa-mina==j-i) res++;
}
}
cout<<res<<endl;
return 0;
}递增三元组
给定三个整数数组
A=[A1,A2,…AN],
B=[B1,B2,…BN],
C=[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k) 满足：
1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式
一个整数表示答案。
数据范围
1≤N≤10^5,
0≤Ai,Bi,Ci≤10^5
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27
//思路:二分 先对三个数组进行sort排序,然后遍历b数组,对于b中的每一个数b[i],在a数组中寻找最后一个
//小于b[i]的数的下标,这里我们记做l.在再c数组中寻找第一个大于b[i]的数的下标,这里我们记做r
//可知a数组中,小于b[i]的数的个数为l+1,c数组中大于b[i]数的个数为n-r.(下标从0开始)
//因此在三元递增组中,以b[i]为中间数的个数为(l+1)*(n-r).
//遍历b数组,res+=(l+1)*(n-r) 即为答案
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], b[N], c[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++) scanf("%d", &b[i]);
for (int i = 0; i < n; i++) scanf("%d", &c[i]);
sort(a, a + n); //二分需要满足单调性
sort(b, b + n);
sort(c, c + n);
LL res = 0; //答案可能会很大,会爆int
for (int i = 0; i < n; i++)
{
int l = 0, r = n - 1; //二分查找a数组中最后一个小于b[i]的数的下标
while (l < r)
{
int mid = (l + r + 1) / 2;
if (a[mid] < b[i]) l = mid;
else r = mid - 1;
}
if (a[l] >= b[i]) //如果未找到小于b[i]的数,将x标记为-1,后续计算时 x+1==0
{
l = -1;
}
int x = l;
l = 0, r = n - 1;
while (l < r)
{
int mid = (l + r) / 2;
if (c[mid] > b[i]) r = mid;
else l = mid + 1;
}
if (c[l] <= b[i]) //如果未找到大于b[i]的数,将y标记为n,后续计算时 n-y==0;
{
r = n;
}
int y = r;
res += (LL)(x + 1)*(n - y);
}
printf("%lld\n", res);
return 0;
}特别数的和
小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0），在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。
请问，在 1 到 n 中，所有这样的数的和是多少？
输入格式
共一行，包含一个整数 n。
输出格式
共一行，包含一个整数，表示满足条件的数的和。
数据范围
1≤n≤10000
输入样例：
40
输出样例：
574
#include <bits/stdc++.h>
using namespace std;
int n,res;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x=i;
while(x)
{
int t=x%10;
x/=10;
if(t==2||t==1||t==0||t==9)
{
res+=i;
break;
}
}
}
cout<<res<<endl;
return 0;
}
