【蓝桥杯】DP和枚举(持续更新~~~)_网站优化分享

DP

DP就是动态规划，其类型有以下两个特征：

重叠子问题：子问题是原大问题的小版本，计算步骤完全一样，计算大问题要多次重复计算小问题。

最优子结构：大问题的最优解包含小问题的最优解，可通过小问题去求解大问题。

0/1背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。

数据范围
00
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

//未优化版本
#include 
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< 
 摘花生 
 
   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 
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< 
 最长上升子序列 
 
   给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。 
  

  输入格式 
  
第一行包含整数 N。 
  
第二行包含 N 个整数，表示完整序列。 
  

  输出格式 
  
输出一个整数，表示最大长度。 
  

  数据范围 
  
1≤N≤1000， 
  
−10^9≤数列中的数≤10^9 
  

  输入样例： 
  
7 
  
3 1 2 1 8 5 6 
  

  输出样例： 
  
4 
  
 #include 
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;ja[j])
                dp[i]=max(dp[i],dp[j]+1);//前一个小于自己的数结尾的最大上升子序列加上自己，即+1
        }
        res=max(res,dp[i]);
    }
    
    cout< 
 枚举 
 连号区间数 
 
   小明这些天一直在思考这样一个奇怪而有趣的问题： 
  
在 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 
using namespace std;
const int N=10010,INF=1e8;
int n;
int a[N];
int main()
{
    cin>>n;
    for(int i=0;i>a[i];
    int res=0;
    for(int i=0;i 
 递增三元组 
 
   给定三个整数数组 
  
A=[A1,A2,…AN], 
  
B=[B1,B2,…BN], 
  
C=[C1,C2,…CN], 
  
请你统计有多少个三元组 (i,j,k) 满足： 
  
1≤i,j,k≤N 
  
Ai
  输入格式 
  
第一行包含一个整数 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
#include
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 
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<  校园网站设计模板  天山网首页  南充房产网南充房产信息网  青岛中小企业网站制作  怎样在百度建立自己的网站  网站建设中应该注意的设计要点

上一篇：求解三维装箱问题的启发式深度优先搜索算法(python)

下一篇：基于扩展卡尔曼滤波的SOC估计（附MATLAB代码）