jjzjj

((蓝桥杯 刷题全集)【备战(蓝桥杯)算法竞赛-第6天(动态规划 专题)】( 从头开始重新做题，记录备战竞赛路上的每一道题 )距离蓝桥杯还有61天

编程浩 2023-07-13 原文

🏆🏆🏆🏆🏆🏆🏆
欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
　
文章字体风格：
红色文字表示：重难点✔★
蓝色文字表示：思路以及想法✔★
　
如果大家觉得有帮助的话，感谢大家帮忙
点赞！收藏！转发！
　
我的qq号是：1210931886，欢迎大家加群，一起学习，互相交流，共同进步🎉🎉✨✨
🥇🥇🥇🥇🥇🥇🥇

蓝桥杯系列，为大家提供

  1. 做题全集，备战蓝桥杯，就做这个系列的题即可
  2. 一个大概的做题规划——大家最好在此基础上提前两个月准备

备战蓝桥杯就刷这些题
第一天博客链接 - 基础算法 -上
第二天博客链接 - 基础算法 -下 + 数据结构专题
第三天博客链接 - 搜索与图论-上 专题
第四天博客链接 - 搜索与图论-下 专题
第五天博客链接 - 数学知识专题
第六天博客链接 - 动态规划 专题
第七天博客链接 - 贪心算法 专题

蓝桥杯 刷题全集

一、背包问题

★f[i][j] 背包容量为j，前i个物品的最大价值

1. 01背包问题(不需要初始化) ✔1.6 ✔1.7

原题链接

f[i][j]怎么想出来
在j体积下 前i个物品的最大价值

一、为什么要从0到v把背包中各种体积下的情况都存储下来呢？（算法理解）
因为我们需要回溯

二、但我们选i的时候，需要明白两件事
选不选第i件物品的判断依据

  1. 当 背包中限定的体积，小于v【i】一定不能选
  2. 当 背包中限定的体积可以装下v[i]时，那么我们就需要知道，到底装下这个价值大，还是不装下这个价值大
    装下的价值 = f[i-1][j-v[i]] + w[i]
    不装下的价值 = f[i-1][j]；

总结：深刻记住 f[i][j] 表示 在j体积中前i个物品下的最大价值

二维

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    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++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

一维

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

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 = m; j >= v[i]; j--) 
            f[j] = max(f[j], f[j-v[i]]+w[i]);
    cout << f[m] << endl;
 return 0;    
}

2. 完全背包问题 ✔1.6

原题链接

一、朴素做法
#include<iostream>
using namespace std;

const int N = 1010;

int n, m;
int dp[N][N], v[N], w[N];

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 = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ )
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
    cout << dp[n][m] << endl;
}
二、二维数组的优化(需要判断j是否大于v[i])
#include<iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n,m;
int w[N],v[N];

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++)
            if(j<v[i])
                f[i][j] = f[i-1][j];
            else
                f[i][j] = max(f[i-1][j],f[i][j-v[i]]+w[i]);
            
    cout << f[n][m];
    
    return 0;
}
三、一维数组的优化
#include<iostream>

using namespace std;

const int N = 1010;

int n,m;
int f[N];
int v[N],w[N];

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 = v[i]; j <= m; j++)
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    
    cout << f[m];
    
    return 0;
}

二维

#include<iostream>

using namespace std;

const int N = 1010;
int f[N][N];
int w[N];
int v[N];
int n,m;

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++)
        {
            if(j < v[i])
                f[i][j] = f[i-1][j];
            else
                f[i][j] = max(f[i-1][j],f[i][j-v[i]]+w[i]);
        }
    }
    cout << f[n][m];
    
    return 0;
}

一维

#include<iostream>

using namespace std;

const int N = 1010;
int f[N];
int w[N];
int v[N];
int n,m;

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 = v[i]; j <= m; j++)
        {
           f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout << f[m];
    
    return 0;
}

怎么由二维变成一维
看更新f[i][j] 需要的是本行数据还是上行数据

3. 多重背包问题 I ✔1.6

原题链接
三重循环(针对的是f[i][j]处理)
★不需要处理j不够的情况

#include<iostream>

using namespace std;

const int N = 110;

int f[N][N],w[N],v[N],s[N];
int n,m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i] >> s[i];
        
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            for(int k = 0; k <= s[i]; k++)
            {
                if(j>=k*v[i])
                    f[i][j] = max(f[i][j],f[i-1][j-k*v[i]] + k*w[i]);
            }
        }
    }
    
    cout << f[n][m];
        
    return 0;
}

4. 多重背包问题 II ✔1.6

s 分解成 哪些数 可以加和表示 1-s

原题链接

#include<iostream>

using namespace std;

const int N = 2*1e6+10;

int f[N],v[N],w[N],s,cnt;
int n,m;

int main()
{
    cin >> n >> m;
    int vv,ww;
    for(int i = 1; i <= n; i++)
    {
        cin >> vv >> ww >> s;
        
        int k = 1;
        while(k <= s)
        {
            v[++cnt] = k*vv;
            w[cnt] = k*ww;
            s -= k;
            k = 2*k;
        }
        if(s)
        {
            v[++cnt] = s*vv;
            w[cnt] = s*ww;
        }
    }
    
    for(int i = 1; i <= cnt; i++)
    {
        for(int j = m; j >= v[i]; j--)
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    }
    cout << f[m];
    return 0;
}

5. 分组背包问题 ✔1.6

原题链接
二维

#include<bits/stdc++.h>
using namespace std;

const int N=110;
int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N],w[N][N],s[N];   //v为体积，w为价值，s代表第i组物品的个数
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];  //读入
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //f[i][j]=f[i-1][j];  //不选
            for(int k=0;k<=s[i];k++){
                if(j>=v[i][k])     f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[n][m]<<endl;
}

一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;

    return 0;
}

二、线性DP

1. 数字三角形 ✔1.6

★f[i][j] 从下到上 走到f[i][j]的所有路径的最大值
原题链接
原题链接

#include<iostream>

using namespace std;

const int N = 510;

int f[N][N];

int main()
{
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            cin >> f[i][j];
    
    for(int i = n-1; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            f[i][j] += max(f[i+1][j],f[i+1][j+1]);
    
    cout << f[1][1];
    
    return 0;
}

2. 最长上升子序列

★双重循环(子序列不一定连续)

★f[i] 以第i个数结尾的 上升子序列的最大值
原题链接
原题链接

#include<iostream>

using namespace std;

const int N = 1010;

int a[N],f[N];

int main()
{
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++)
        cin >> a[i];
        
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j <= i; j++)
        {
            if(a[i] > a[j])
                f[i] = max(f[i],f[j]+1);
        }
    }
    
    int res = 0;
    
    for(int i = 1; i <= n; i++)
        res = max(res,f[i]);
        
    cout << res;
    
    return 0;
}

3. 最长上升子序列 II ✔1.6

★f[i] 存储 最长上升子序列的 示范串
★ 二分 + dp优化

原题链接

#include<iostream>

using namespace std;

const int N = 100010;

int a[N],q[N];
int n;

int main()
{
    cin >> n;
    
    for(int i = 1; i <= n; i++)
        cin >> a[i];
        
    int len = 1;
    for(int i = 1; i <= n; i++)
    {
        int l = 1,r = len;
        int mid;
        while(l < r)
        {
            mid = (l+r)/2;
            if(q[mid] >= a[i])
                r = mid;
            else
                l = mid + 1;
        }
        len = max(r+1,len);
        q[r] = a[i];
    }
    
    cout << len-1;
}

4. 最长公共子序列 ✔1.6

★f[i][j]表示a的前i个字母，和b的前j个字母的最长公共子序列长度

原题链接

思路 (在推导示例时，可以总结出)
  1. f[i][j] 表示什么需要先想清楚。
    表示的是：在i，j组合的情况下，的最大子串 长度
    所以当 i，j相等时
    f[i][j] = f[i-1][j-1] + 1
    不相等的时候
    f[i][j] = max(f[i-1][j],f[i][j-1]);
#include<iostream>

using namespace std;

const int N = 1010;

int f[N][N];
int n,m;
char a[N],b[N];

int main()
{
    cin >> n >> m >> a+1 >> b+1;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i]==b[j])
                f[i][j] = f[i-1][j-1] + 1;
            else
                f[i][j] = max(f[i-1][j],f[i][j-1]);
        }
    }
    
    cout << f[n][m];
    
    return 0;
}

5. 最短编辑距离 ✔1.6

原题链接

★f[i][j] 所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合
做题总结：f[i-1][j] 到 f的距离 和 f[i][j-1] 到f的距离差很远
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%s", &n, a + 1);
    scanf("%d%s", &m, b + 1);

    for (int i = 0; i <= m; i ++ ) f[0][i] = i;
    for (int i = 0; i <= n; i ++ ) f[i][0] = i;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (a[i] == b[j])
            {
                f[i][j] = f[i-1][j-1];
            }
            else
            {
                f[i][j] = min(f[i-1][j] + 1, f[i - 1][j - 1] + 1);
                f[i][j] = min(f[i][j],f[i][j-1]+1);
            }
        }

    printf("%d\n", f[n][m]);

    return 0;
}

6. 编辑距离

★f[i][j] 所有把a中的前i个字母 变成 b中前j个字母的集合的操作集合

原题链接

三、区间dp

  1. 遍历区间长度值
  2. 遍历左端点
    得到右端点
  3. 遍历左右端点之间的值

1. 石子合并

★f[i][j]表示将 i 到 j 合并的最小值

原题链接
原题链接

区间dp的套路
  1. 先遍历区间长度
  2. 遍历区间左端点，由左端点+区间长度 找到右端点

本题

  1. 求f[i][j] 是求从i到j 中取哪个k值使得总和最小，
    所以要遍历i到j中的 每个值（用k遍历）
#include <iostream>
#include <cstring>

using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] += s[i - 1] + a[i];
    }

    memset(f, 0x3f, sizeof f);
    // 区间 DP 枚举套路：长度+左端点 
    for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数
        for (int i = 1; i + len - 1 <= n; i ++) {
            int j = i + len - 1; // 自动得到右端点
            if (len == 1) {
                f[i][j] = 0;  // 边界初始化
                continue;
            }

            for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout << f[1][n] << endl;


    return 0;
}

四、计数类DP

题解

★1. 整数划分

★f[i][j] 表示 背包为j的 前i个物品 的方案数

f[i][0] 是1
#include<iostream>

using namespace std;

const int N = 1010,mol = 1e9+7;

int f[N][N];
int n;

int main()
{
    cin >> n;
    
    for(int i = 1; i <= n; i++) f[i][0] = 1;
    
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = f[i-1][j] % mol;
            if(j >= i)
                f[i][j] = (f[i-1][j] + f[i][j-i])% mol; 
        }
    }
    
    cout << f[n][n];
}
蓝桥备战spanclasstoken蓝桥杯算法职场和发展

有关((蓝桥杯 刷题全集)【备战(蓝桥杯)算法竞赛-第6天(动态规划 专题)】( 从头开始重新做题，记录备战竞赛路上的每一道题 )距离蓝桥杯还有61天的更多相关文章

  1. ruby - Sinatra:运行 rspec 测试时记录噪音 - 2

    Sinatra新手；我正在运行一些rspec测试，但在日志中收到了一堆不需要的噪音。如何消除日志中过多的噪音？我仔细检查了环境是否设置为:test，这意味着记录器级别应设置为WARN而不是DEBUG。spec_helper:require"./app"require"sinatra"require"rspec"require"rack/test"require"database_cleaner"require"factory_girl"set:environment,:testFactoryGirl.definition_file_paths=%w{./factories./test/

  2. ruby-on-rails - Rails 5 Active Record 记录无效错误 - 2

    我有两个Rails模型，即Invoice和Invoice_details。一个Invoice_details属于Invoice，一个Invoice有多个Invoice_details。我无法使用accepts_nested_attributes_forinInvoice通过Invoice模型保存Invoice_details。我收到以下错误:(0.2ms)BEGIN(0.2ms)ROLLBACKCompleted422UnprocessableEntityin25ms(ActiveRecord:4.0ms)ActiveRecord::RecordInvalid(Validationfa

  3. ruby-on-rails - 事件记录 : Select max of limit - 2

    我正在尝试将以下SQL查询转换为ActiveRecord，它正在融化我的大脑。deletefromtablewhereid有什么想法吗？我想做的是限制表中的行数。所以，我想删除少于最近10个条目的所有内容。编辑:通过结合以下几个答案找到了解决方案。Temperature.where('id这给我留下了最新的10个条目。 最佳答案 从您的SQL来看，您似乎想要从表中删除前10条记录。我相信到目前为止的大多数答案都会如此。这里有两个额外的选择:基于MurifoX的版本:Table.where(:id=>Table.order(:id).

  4. Ruby 守护进程导致 ActiveRecord 记录器 IOError - 2

    我目前正在用Ruby编写一个项目，它使用ActiveRecordgem进行数据库交互，我正在尝试使用ActiveRecord::Base.logger记录所有数据库事件具有以下代码的属性ActiveRecord::Base.logger=Logger.new(File.open('logs/database.log','a'))这适用于迁移等(出于某种原因似乎需要启用日志记录，因为它在禁用时会出现NilClass错误)但是当我尝试运行包含调用ActiveRecord对象的线程守护程序的项目时脚本失败并出现以下错误/System/Library/Frameworks/Ruby.frame

  5. ruby-on-rails - 在 Rails 中更高效地查找或创建多条记录 - 2

    我有一个应用需要发送用户事件邀请。当用户邀请friend(用户)参加事件时，如果尚不存在将用户连接到该事件的新记录，则会创建该记录。我的模型由用户、事件和events_user组成。classEventdefinvite(user_id,*args)user_id.eachdo|u|e=EventsUser.find_or_create_by_event_id_and_user_id(self.id,u)e.save!endendend用法Event.first.invite([1,2,3])我不认为以上是完成我的任务的最有效方法。我设想了一种方法，例如Model.find_or_cr

  6. ruby - 在模块/类之间共享全局记录器 - 2

    在许多ruby​​类之间共享记录器实例的最佳(正确)方法是什么？现在我只是将记录器创建为全局$logger=Logger.new变量，但我觉得有更好的方法可以在不使用全局变量的情况下执行此操作。如果我有以下内容:moduleFooclassAclassBclassC...classZend在所有类之间共享记录器实例的最佳方式是什么？我是以某种方式在Foo模块中声明/创建记录器还是只是使用全局$logger没问题？ 最佳答案 在模块中添加常量:moduleFooLogger=Logger.newclassAclassBclassC..

  7. ruby - Sinatra 中的全局救援和日志记录异常 - 2

    如何在出现异常时指定全局救援，如果您将Sinatra用于API或应用程序，您将如何处理日志记录？ 最佳答案 404可以在not_found方法的帮助下处理，例如:not_founddo'Sitedoesnotexist.'end500s可以通过调用带有block的错误方法来处理，例如:errordo"Applicationerror.Plstrylater."end错误的详细信息可以通过request.env中的sinatra.error访问，如下所示:errordo'Anerroroccured:'+request.env['si

  8. ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2

    例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果

  9. ruby-on-rails - ActiveRecord 如何将现有记录添加到 has_many :through relationship in rails? 中的关联 - 2

    在我的Rails项目中，我有三个模型:classRecipe:recipe_categorizationsaccepts_nested_attributes_for:recipe_categories,allow_destroy::trueendclassCategory:recipe_categorizationsendclassRecipeCategorization通过这个简单的has_many:through设置，我怎样才能像这样获取给定的食谱:@recipe=Recipe.first并根据现有类别向此食谱添加类别，并在相应类别上对其进行更新。所以:@category=#Exi

  10. ruby-on-rails - 使用 Rails 事件记录获取二级模型 - 2

    我有一个帖子属于城市的关系，城市又属于一个州，例如:classPost现在我想找到所有帖子及其所属的城市和州。我编写了以下查询来获取带有城市的帖子，但不知道如何在同一查找器中获取带有城市的相应州:@post=Post.find:all,:include=>[:city]感谢任何帮助。谢谢。 最佳答案 Post.all(:include=>{:city=>:state}) 关于ruby-on-rails-使用Rails事件记录获取二级模型，我们在StackOverflow上找到一个类似的问

随机推荐