【蓝桥杯】DP和枚举(持续更新~~~)

😽
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;
}