那些正常的动态规划

目录

• 前言
  
  
  
  • 动态规划到底是啥？
    
  
  
• 线性dp
  
  
  
  • 最长上升子序列
    
    
    
    • 子集和子序列和子串的区别
      
    • 内容分析
      
    
    
  • 最大上升子序列
    
  • 例题1——[NOIP200#include<bits/stdc++.h>
    using namespace std;
    
    int a[10010],dp[10010],ans=INT_MIN;
    int main(){
            int n;
            cin>>n;
            for (int i=1;i<=n;i++){
                    cin>>a;
                    dp=a;
            }       
            for (int i=1;i<=n;i++){
                    for (int j=1;j<i;j++){
                            if (a[j] 提高组] 合唱队形
    
    
    
    • 分析
      
    
    
  • 最长公共子序列
    
  • 最长公共子串
    
  
  
• 平面dp
  
  
  
  • 例题2——[NOIP2000 提高组] 方格取数
    
    
    
    • 分析
      
    
    
  • 例题3——[NOIP2008 提高组] 传纸条
    
    
    
    • 分析
      
    
    
  • 例题#include<bits/stdc++.h>
    using namespace std;
    
    int a[10010],dp[10010],ans=INT_MIN;
    int main(){
            int n;
            cin>>n;
            for (int i=1;i<=n;i++){
                    cin>>a;
                    dp=a;
            }       
            for (int i=1;i<=n;i++){
                    for (int j=1;j<i;j++){
                            if (a[j]——最大加权矩形
    
    
    
    • 分析
      
      
      
      • 补充：最大字段和
        
      • 最大子矩阵和和最大字段和的关联
        
      
      
    
    
  • 例题5——最大全1子矩阵
    
    
    
    • 分析
      
    
    
  • 例题6——穿衣服
    
    
    
    • 分析
      
    
    
  
  
• 背包问题
  
  
  
  • 什么是背包问题
    
  • 背包的分类
    
  • 01背包
    
    
    
    • 思路一
      
    • 思路二
      
    • 思路三（重头戏）
      
      
      
      • 常规代码
        
      • 空间优化
        
      
      
    
    
  • 例题7——[NOIP2001 普及组] 装箱问题
    
    
    
    • 分析
      
    
    
  • 例题8——最大约数和
    
    
    
    • 分析
      
    
    
  • 多重背包
    
    
    
    • 
      
      
      
      • 位置1
        
      • 位置2
        
      
      
    • 二进制优化
      
    • 完整代码
      
    
    
  • 例题9——[NOIP1996 提高组] 砝码称重
    
    
    
    • 分析
      
    
    
  • 完全背包
    
    
    
    • 优化
      
      
      
      • 优化办法一
        
      • 优化办法二（重点）（敲黑板）
        
      
      
    
    
  • 例题10——疯狂的采药
    
    
    
    • 分析
      
    
    
  • 混合背包
    
  • 多维背包
    
  • 例题11——「一本通入门 2.9.2」 潜水员
    
    
    
    • 分析
      
    
    
  • 分组背包
    
  • 例题12——旅行者
    
    
    
    • 分析
      
    
    
  • 泛化背包
    
  • 例题13——精力的分配
    
    
    
    • 分析
      
    
    
  • 有依赖的背包
    
  • 例题1#include<bits/stdc++.h>
    using namespace std;
    
    int a[10010],dp[10010],ans=INT_MIN;
    int main(){
            int n;
            cin>>n;
            for (int i=1;i<=n;i++){
                    cin>>a;
                    dp=a;
            }       
            for (int i=1;i<=n;i++){
                    for (int j=1;j<i;j++){
                            if (a[j]——[NOIP2006 提高组] 金明的预算方案
    
    
    
    • 分析
      
    
    
  • 背包方案数
    
  • 例题15——方案数
    
    
    
    • 分析
      
    
    
  • 01背包问题输出方案
    
  • 背包问题总结
    
  
  
• 区间dp
  
  
  
  • 区间型动态规划的特点：
    
  • 例题16——一本通改编——衣服合并
    
    
    
    • 分析
      
    
    
  • 小结1
    
  • 例题17——1275：【例9.19】乘积最大
    
    
    
    • 分析
      
    
    
  • 小结2
    
  • 例题18——[IOI2000] 回文字串
    
    
    
    • 分析
      
    
    
  • 环形区间dp
    
  • 例题19——[NOI1995] 石子合并
    
    
    
    • 分析
      
    
    
  • 例题20——[NOIP2006 提高组] 能量项链
    
    
    
    • 分析
      
    
    
  • 例题21——[NOIP2001 提高组] 数的划分
    
    
    
    • 分析
      
    
    
  • 例题22——放苹果
    
    
    
    • 分析
      
    
    
  
  

前言

在说线性dp之前，我们先来聊一聊动态规划是啥？
动态规划到底是啥？

动态规划是普及组内容中最难的一个部分，也是每年几乎必考的内容。它对思维的要求极高，它和图论、数据结构不同的地方在于它没有一个标准的数学表达式和明确清晰的解题方法。
动态规划是对求解最优解的一种途径，而不是一种特殊的算法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的阶梯方法，而不存在一种万能的动态规划算法。为了方便学习，我们把若干具有代表性的动态规划问题归纳总结成不同的几类，并建立对应的数学模型。
动态规划一般用来求解多阶段决策问题的最优解，可以将过程分成若干个互相联系的阶段，在它的每一阶段都需要做决策，从而使整个过程达到最好的活动效果。各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。

[attach]27#include<bits/stdc++.h>
using namespace std;

int a[10010],dp[10010],ans=INT_MIN;
int main(){
        int n;
        cin>>n;
        for (int i=1;i<=n;i++){
                cin>>a;
                dp=a;
        }       
        for (int i=1;i<=n;i++){
                for (int j=1;j<i;j++){
                        if (a[j]1#include<bits/stdc++.h>
using namespace std;

int a[10010],dp[10010],ans=INT_MIN;
int main(){
        int n;
        cin>>n;
        for (int i=1;i<=n;i++){
                cin>>a;
                dp=a;
        }       
        for (int i=1;i<=n;i++){
                for (int j=1;j<i;j++){
                        if (a[j][/attach]

对于动态规划问题，最重要的是分析出：
一、决策对象：我们需要对题目中的哪个变量进行决策。
二、阶段：需要将问题的全过程恰当的分成若干个相互联系的阶段，以便按一定的次序去求解。阶段的划分一般是根据时间(先后顺序) 和 空间(大小关系) 的自然特征来划分。
三、状态：某一阶段的出发位置称为状态，一个阶段可能包含多个状态，状态大多都是用 数组 来表示，即表示我们需要的答案。
四、决策：分析完问题后我们应该怎么解决问题。
五、状态转移方程：描述前一阶段到后一阶段的状态演变规律。
线性dp

线性动态规划是动态规划中比较简单的一类问题，他的状态转移是线性的，即状态的转移是固定的，常见的如从前到后，或者从后到前。线性动态规划和递推比较类似，在很多情况下，这两种做法大致是相同的。一般的，递推是当前要求解的答案和前面某个固定答案有关，而线性动态规划是当前答案和前面的某个答案存在关系，这个位置在不同的情况下是不相同的。
最长上升子序列

言归正传，我们继续聊线性dp。
[size=#include<bits/stdc++.h>
using namespace std;

int a[10010],dp[10010],ans=INT_MIN;
int main(){
        int n;
        cin>>n;
        for (int i=1;i<=n;i++){
                cin>>a;
                dp=a;
        }       
        for (int i=1;i<=n;i++){
                for (int j=1;j<i;j++){
                        if (a[j]]子集和子序列和子串的区别

以\(abfsgegsas\)为例，\(faggas\)是它的子集，因为子集是不计顺序的，\(abggss\) 则是他的子序列，因为子序列是要求有顺序的，而\(abf\)则是他的字串
[size=#include<bits/stdc++.h>
using namespace std;

int a[10010],dp[10010],ans=INT_MIN;
int main(){
        int n;
        cin>>n;
        for (int i=1;i<=n;i++){
                cin>>a;
                dp=a;
        }       
        for (int i=1;i<=n;i++){
                for (int j=1;j<i;j++){
                        if (a[j]]内容分析

决策对象
每个位置上的数。
阶段
共有 \(n\) 个数，因此有 \(n\) 个阶段。
状态
因为每个数都有可能是子序列的结尾，所以使用 dp 表示以第 \(i\) 个数作为结尾的最长上升子序列的长度。
决策
如果以第 \(i\) 个数作为结尾，那么在这个序列中，上一个数一定要小于 \(a\)。因此，我们需要在前面的数中找到比 \(a\) 小的数，而且我们应该选择以这个数结尾的最长上升子序列中最长的那个，这样接在这个数后面得到的序列也是最长的。
状态转移方程
如果 \(h[k]>n;        for (int i=1;i>a;                dp=1;        }                for (int i=1;in;        for (int i=1;i>a;                dp=a;        }                for (int i=1;it_k(1\le i\le k)\)。
你的任务是，已知所有 \(n\) 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
共二行。
第一行是一个整数 \(n\)（\(2\le n\le100\)），表示同学的总数。
第二行有 \(n\) 个整数，用空格分隔，第 \(i\) 个整数 \(t_i\)（\(130\le t_i\le230\)）是第 \(i\) 位同学的身高（厘米）。
输出格式
一个整数，最少需要几位同学出列。
样例 #1
样例输入 #1

1. #include<bits/stdc++.h>
2. using namespace std;
4. int a[10010],dp[10010],ans=INT_MIN;
5. int main(){
6.         int n;
7.         cin>>n;
8.         for (int i=1;i<=n;i++){
9.                 cin>>a[i];
10.                 dp[i]=1;
11.         }       
12.         for (int i=1;i<=n;i++){
13.                 for (int j=1;j<i;j++){
14.                         if (a[j]

复制代码

样例输出 #1

1. #include<bits/stdc++.h>
2. using namespace std;
4. int a[10010],dp[10010],ans=INT_MIN;
5. int main(){
6.         int n;
7.         cin>>n;
8.         for (int i=1;i<=n;i++){
9.                 cin>>a[i];
10.                 dp[i]=a[i];
11.         }       
12.         for (int i=1;i<=n;i++){
13.                 for (int j=1;j<i;j++){
14.                         if (a[j]

复制代码

提示
对于 \(50\%\) 的数据，保证有 \(n \le 20\)。
对于全部的数据，保证有 \(n \le 100\)。
[size=#include<bits/stdc++.h>
using namespace std;

int a[10010],dp[10010],ans=INT_MIN;
int main(){
        int n;
        cin>>n;
        for (int i=1;i<=n;i++){
                cin>>a;
                dp=a;
        }       
        for (int i=1;i<=n;i++){
                for (int j=1;j<i;j++){
                        if (a[j]]分析


该题实际上就是前面求一个最长上升子序列，对后面求一个最长下降子序列。但是问题在于这两个序列的连接点我们不知道，没有办法直接求解出来，也就是说任意一个点都有可能作为这个连接点，所以我们需要先枚举这个连接点x，再分别对区间[1,x]求最长上升子序列，对区间[x+1,n]求最长下降子序列。这种做法的时间复杂度为O(n3),但是该题的数据范围改为n>n;        for (int i=1;i>a;                dp1=1;                dp2=1;        }        for (int i=1;ia[j]){                                dp2=max(dp2,dp2[j]+1);                        }                }        }        for (int i=n;i>=1;i--){                minn=min(n-dp1-dp2,minn);        }                couta>>b;    dp[0][0]=0;    for (int i=1;ib;        dp[0][0]=0;        for (int i=1;i>n;        while (1){                int a,b,c;                cin>>a>>b>>c;                if (a==0&&b==0&&c==0)break;                mp[a]=c;        }        for (int i=1;ib>>c;                if (a==0&&b==0&&c==0)break;                mp[a]=c;        }        for (int i=1;i