蓝桥杯省赛在即练习一道动态规划经典题型之一

具体来说，使用数组 b[] 记录以每个位置 i 结尾的子序列的最大和。初始时，将 b[i] 初始化为 a[i]，为什么呢？？

因为以单个元素结尾的子序列的最大和就是该元素本身。这个是重点

状态转移方程：通过遍历数组 a[] 中的每个元素 a[i]，并与之前的元素 a[j] (j < i) 进行比较。如果 a[i] 大于 a[j]，意味着可以将 a[i] 加入到以 a[j] 结尾的子序列中，从而得到以 a[i] 结尾的子序列。此时，更新 b[i] 为 b[j] + a[i]，即将以 a[j] 结尾的子序列的最大和加上 a[i]。这样可以保证 b[i] 记录的是以 a[i] 结尾的子序列的最大和。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ll n;cin>>n;
  ll a[n];
  ll b[n];
  for(int i=1;i<=n;++i){
    cin>>a[i];
    b[i]=a[i];
  }
  for(int i=1;i<=n;++i){
    for(int j=1;j<=i;++j){j是看在当前元素前面的值会不会有比它大的，好进行后面的状态转移
      if(a[i]>a[j]){当前的元素比前面的元素都大的话就可以加入b数组
        b[i]=max(b[i],b[j]+a[i]);b数组存放的是前i结尾的子序列结尾的最大和
b[j]+a[i]这个这样来理解当前以前面j结尾的最大和，加上当前a[i]如果大于b[j]的话，就会更新最大值
      }
    }
  }
  ll ans=*max_element(b+1,b+1+n);找到数组中最大的元素之和
  cout<<ans;
  return 0;
}

为什么我们说这个是经典的动态规划呢

首先我们要找到有递增的元素的下标，而且在元素下标增大的同时元素也要递增

如果我们采用暴力肯定是不可取的，这也可以是一个题型，记住就行了，就跟我们做数学题一样

先开始的我是用优先队列来写的，但是没有过，还是给大家看看吧我怎么出错的

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;cin>>n;
  int a[n];
  priority_queue<pair<int,int>>qp;
  for(int i=0;i<n;++i){
    int num1=i;
    int num=0;cin>>num;
    qp.push(make_pair(num1,num));//优先队列
  }
  for(int i=0;i<n;++i){
    int ans=0;
    auto[a,b]=qp.top();
    qp.pop();//最大的找不到就扔了
    auto[a1,b1]=qp.top();
    qp.pop();
    auto[a2,b2]=qp.top();
    qp.pop();
    auto[a3,b3]=qp.top();
    qp.pop();
    if(a>a1&&a1>a2&&a2>a3){//&&b>b1&&b1>b2&&b2>b3){
      // ans=b+b1+b2+b3;
      // cout<<ans;
      if(b>b1&&b1>b2&&b2>b3){
        ans=b+b1+b2+b3;
        cout<<ans;
      //cout<<a<<" "<<a1<<" "<<a2<<" "<<a3;
      //cout<<b<<" "<<b1<<" "<<b2<<" "<<b3;
      return 0;
    }
  }
    qp.push(make_pair(a1,b1));
    qp.push(make_pair(a2,b2));
    qp.push(make_pair(a3,b3));
  }
  return 0;
}

优先队列我只可以找到连续的下标或者递增的元素，我不知道怎么把这2者加起来，如果我想二者同时要得到也就是，如果我同时要得到数组元素的下标是连续的并且元素的值也是连续的，那么代码就会报错。我调试了代码才明白的哈哈哈哈，也是进步了。