秋招突击——算法打卡——5/31——复习{采药问题、(状态压缩DP)小国王}——新做:{盛最多水的容器、整数转罗马数字}

文章目录

    • 复习
      • 背包模型——采药问题
      • 状态压缩DP——小国王
        • 思路分析
        • 实现代码参考
    • 新作
      • 盛最多的水
        • 个人实现
          • 思路分析
          • 实现代码
        • 参考分析
          • 思路分析
          • 实现思路
      • 整数转罗马数字
        • 个人实现
          • 思路分析
          • 实现代码
        • 参考实现
          • 思路分析
          • 实现代码
    • 总结

复习

背包模型——采药问题

  • 原题链接
  • 这里回忆的时候,还是有点问题,就是起点值怎么写?并不确定!
  • 然后关于这个表达式,也是弄了半天才想起来,还是要多多练习一下!
#include <iostream>
#include <algorithm>

using namespace std;
const int T = 1010;
const int M = 110;
int t[M],w[M];
int f[M][T];
int f1[T];
int n,m;

int main(){
    cin>>n>>m;
    for (int i = 1; i <= m; ++i) {
        cin>>t[i]>>w[i];
    }

    // 遍历所有的药物
    // f[i][j]:表示在前i个物体下,容量为j的若干种装法中,最高的价值
    // 集合划分,对于第i个物体而言,也就是两种情况,装或者不装,装f[i-1][j - t[i]] + w[i],不装f[i-1][j]
    int res = 0;
    for (int i = 1; i <= m; ++i) {
        // 什么时候置零是一个问题,不知道怎么办
        f[i][0] = 0;
        for (int j = 1; j <= n && t[i] <= j; ++j) {
            f[i][j] = max(f[i-1][j],f[i -1][j - t[i]] + w[i]);
            res = max(res ,f[i][j]);
        }
    }
    cout<<res;

    // 使用滚动矩阵进行优化
    for (int i = 1; i <= m ; ++i) {
        for (int j = n; j >=  1 && t[i] <= j; j--) {
            f1[j] = max(f1[j],f1[j - t[i]] + w[i]);
        }
    }
    cout<<f[n]<< endl;
}
  • 关于二维数组,基本思路是对的,就分两种情况,装或者不装,但是你得分开写
    参考信息
    在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

状态压缩DP——小国王

  • 题目内容
    在这里插入图片描述
思路分析
  • 参考链接:状态压缩
  • 这道题是真的不会,当时听了半天都没听懂,然后直接跳过了,但是也是dp的一种,经常考,还是要学习一下啊。
  • 这里是使用二进制表示某一个行数的棋盘的状态

在这里插入图片描述

  • 今天是不可能完全搞懂了,就搞懂局部吧,半个小时能懂多少懂多少,不然没时间搞别的东西了。再看一遍,也觉得是昏了头了,即使要是考了这个,直接跳过吧。

  • 第i行的摆放位置,仅仅和第i-1行是有关系的,所以仅仅需要考虑第i-1的状态

  • 第i行可以摆放x中状态,然后在判断一下是否和第i-1行是合法的,然后在进行累加,所以需要干两件事

    • 检查第i行的状态和第i-1行状态是否是合法的
    • 第i行有哪些合法状态
      暂时就分析到这里,明天就是看看代码还有怎么计算预设的状态转换了。 请添加图片描述
      请添加图片描述
实现代码参考
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 11, M = 1 << N, C = N * N;

int n, m, K;
LL f[N][C][M];
int cnt[M];
vector<int> legal_state;
vector<int> state_trans[M];

bool check(int state)
{
    return !(state & state >> 1);
}
int count(int state)
{
    int res = 0;
    for (int i = 0; i < n; ++ i) res += state >> i & 1;
    return res;
}
int main()
{
    cin >> n >> K;
    //预处理所有合法状态
    for (int st = 0; st < 1 << n; ++ st)
        //检查当前状态是否合法
        if (check(st))
            legal_state.push_back(st),
            cnt[st] = count(st);
    m = legal_state.size();
    //预处理所有合法状态的合法转移
    for (auto cur_st: legal_state)
        for (auto to_st: legal_state)
            if (!(cur_st & to_st) && check(cur_st | to_st))//上下不相邻且纵坐标也不相邻
                state_trans[cur_st].push_back(to_st);
    //动态规划
    f[0][0][0] = 1;
    for (int i = 1; i <= n; ++ i)
        for (int j = 0; j <= K; ++ j)
            for (auto &state: legal_state)
                for (auto &pre_st: state_trans[state])
                    if (j - cnt[state] >= 0)
                        f[i][j][state] += f[i - 1][j - cnt[state]][pre_st];
    //统计目标状态的所有方案数
    LL res = 0;
    for (auto state: legal_state) res += f[n][K][state];
    cout << res << endl;
    return 0;
}

作者:一只野生彩色铅笔
链接:https://www.acwing.com/solution/content/56348/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

新作

盛最多的水

题目链接
在这里插入图片描述

个人实现
思路分析
  • 不像是动态规划,最直白的做法是进行暴力搜索的,但是问题空间的达到了10的10次方,有点爆炸,想想看怎么减少,但是就算去掉重复的,也是10的9次方。
  • 对了,这个可以试试看双向指针,两边,哪边移动会变大,就移动哪边,移动之后,在计算一下体积有没有变大
  • 双指针没想清楚,但是后来想清楚了,应该先找到最大值和次大值,然后分别向两边进行遍历,因为很显然,在最大值和次大值中间的数字,任何容积都是比这两个小的。所以只有可能向两边进行遍历。但是这里写的有点慢,就是求第二大的数字的时候,没写好,看看有什么更方便的方式。
  • 这里有个问题
    • 并不知道怎么移动左右指标比较合理!!
实现代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100000;
int maxArea(vector<int>& h) {
    // 定义双指针
    int first = INT_MIN,second = INT_MIN,firstIdx,secondIdx;
    for (int i = 0; i < h.size(); ++i) {
        if (h[i] > first )   first = h[i] , firstIdx = i;
        if (h[i] > second && h[i] < first )   second = h[i] , secondIdx = i;
    }
    
    int l = min(firstIdx,secondIdx),r = max(firstIdx,secondIdx);
    int len ,vol = 0;
    while(l >= 0 || r < h.size()){
        len = r - l;
        int temp = min(h[l],h[r]) * len;
        vol = vol < temp ? temp:vol;
        // 然后根据情况进行迁移
        // 关于这里如何移动,并不知道怎么调整
        if (h[l] < h[l + 1])    l --;
        if (h[r] < h[r - 1])    r ++;
    }
    return vol;
}

int main(){
    vector<int> n = {1,8,6,2,5,4,8,3,7};
    cout<<maxArea(n)<<endl;
}
参考分析
思路分析
  • 好吧,我想多了,我这样做并不是最优的,是双指针,但是是从两边开始往中间移动的双指针,而且是两个指针进行比较,那个指针的数值比较低,然后移动哪一个?
  • 证明过程比较形象,具体如下:
    • 用反证法,假设一个最优值,然后一边先到达最优值,然后在控制另外一边进行到达,然后反正在移动过程中不存在最优值
实现思路
int maxArea(vector<int>& h) {
    // 定义双指针
    int vol = 0,l = 0,r = h.size() - 1 ,len = 0;
    while(l < r){
        len = r - l;
        int temp = min(h[l],h[r]) * len;
        vol = vol < temp ? temp:vol;
        // 然后根据情况进行迁移
        // 关于这里如何移动,并不知道怎么调整
        if (h[l] < h[r])    l ++;
        else    r --; 
    }
    return vol;
}

整数转罗马数字

  • 题目链接:整数转罗马数字
    在这里插入图片描述
个人实现
思路分析
  • 数字并不是很大,所以直接进行遍历,逐个位数进行修改
  • 直接暴力做
实现代码

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 3999;
string intToRoman(int num) {
    // 不是4或者9开头,就减去最大值,并将该符号附加到结果,减去其值,将其与部分转换为罗马数字

    // 4或者9开头,使用减法形式

    // 只有10的次方可以连续出现三次,其他都不行

    // 将数字分成几个段落:
    // 1-3 ,可以使用最高位进行连续相加
    // 4:5-1
    // 6-8:5+1-3的组合
    // 9:10-1

    // 先处理1000,确定最高位
    int v = num / 1000,res = num % 1000;
    string s = "";
    if (v <= 3 && v >0)
        while(v)    s += "M" , v--;

    // 然后在获取百位
    v = res / 100,res %= 100;
    switch (v) {
        case 0:
            break;
        case 1:
        case 2:
        case 3:
            while(v){
                s += "C" , v--;
            }
            break;
        case 4:
            s += "CD";
            break;
        case 5:
            s += "D";
            break;
        case 6:
            s += "DC";
            break;
        case 7:
            s += "DCC";
            break;
        case 8:
            s += "DCCC";
            break;
        case 9:
            s += "CM";
            break;
    }

    // 然后在获取十位
    v = res / 10,res %= 10;
    switch (v) {
        case 0:
            break;
        case 1:
        case 2:
        case 3:
            while(v){
                s += "X" , v--;
            }
            break;
        case 4:
            s += "XL";
            break;
        case 5:
            s += "L";
            break;
        case 6:
            s += "LX";
            break;
        case 7:
            s += "LXX";
            break;
        case 8:
            s += "LXXX";
            break;
        case 9:
            s += "XC";
            break;
    }

    //然后在处理个位
    switch (res) {
        case 0:
            break;
        case 1:
        case 2:
        case 3:
            while(v){
                s += "I" , res--;
            }
            break;
        case 4:
            s += "IV";
            break;
        case 5:
            s += "V";
            break;
        case 6:
            s += "VI";
            break;
        case 7:
            s += "VII";
            break;
        case 8:
            s += "VIII";
            break;
        case 9:
            s += "IX";
            break;
    }

    return s;

}
int main(){
    int n = 1;
    cout<<intToRoman(n)<<endl;
}
参考实现
思路分析
  • 这是一道模拟的题目,也就是找规律的题目。规则有限,直接打表也行
    *
  • 但是这里是定义结果临界值,如果大于特定的值,就减去对应的值,

在这里插入图片描述

实现代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 3999;
string intToRoman(int n) {
    string s = "";
    int num[] = {
            1,4,5,9,
                 10,40,50,90,
                 100,400,500,900,
                 1000
                 };
    string numRep[] = {
            "I","IV","V","IX",
            "X","XL","L","XL",
            "C","CD","D","CM",
            "M"};

    for (int i = 12; i >=  0; i --) {
        while(n >= num[i]){
            s += numRep[i];
            n -= num[i];
        }
    }

    cout<<s<<endl;
}
int main(){
    int n = 1;
    cout<<intToRoman(n)<<endl;
}

总结

  • 本来应该坚持一下,但是最近一直在忙论文,本来已经写好了,就差试验了,结果今天把实验做完了,发现实验效果差的不行,因该是方法不行,很难受,不过秋招在即,没什么时间了,就暂时放弃了。明天开始继续跟上了。毕竟论文已经投了,这是第二篇,就是没人给我看,我害怕自己毕不了业,中不了,所以才想写第二篇。不过现在看,每天抽点时间做实验吧,能成就成,不能成也没有办法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/673610.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

回溯算法之简单组合

哦吼&#xff01;今天结束了二叉树&#xff0c;开始回溯算法 其实也需要用到迭代&#xff0c;哈哈哈哈&#xff0c;但是这个暴力穷举真的好爽。 先记一下回溯算法的基本框架吧 老规矩&#xff1a; 还是有结束条件 但是后面就不太一样了 这里就是for循环&#xff0c;循环n…

系统思考的魅力

“不管你信不信&#xff0c;你的系统正是为了现在这个结果而设计的。”—爱德华兹戴明 在长期的组织辅导中&#xff0c;最开始我常听到管理者们说&#xff1a;“这是某某的问题”&#xff0c;或者“某某真不行”。我想这也正显示出系统思考的真正魅力&#xff0c;当大家开始用…

小波相干性显著性检验(MATLAB R2018A)

交叉小波常被用于检测不同信号之间的相关性&#xff0c;其在时频域建立了不同信号之间的联系。对于两个时域信号&#xff0c;其交叉小波变换和交叉小波尺度谱如下&#xff1a; 以轴承振动信号为例&#xff0c;利用正常轴承与故障轴承的振动信号、故障轴承和故障轴承的振动信号分…

使用conda环境安装pythonocc-core

conda环境安装pythonocc库 基本环境 操作系统:Ubuntu 22.04 conda 23.11.0 安装pythonocc-core conda create --name pyocc python3.10 conda activate pyocc conda install -c conda-forge pythonocc-core7.8.1也可参考下面的官方地址 pythonocc-core 官方git地址 conda官…

Golang | Leetcode Golang题解之第128题最长连续序列

题目&#xff1a; 题解&#xff1a; func longestConsecutive(nums []int) int {numSet : map[int]bool{}for _, num : range nums {numSet[num] true}longestStreak : 0for num : range numSet {if !numSet[num-1] {currentNum : numcurrentStreak : 1for numSet[currentNum…

第4章:车辆的横向优化控制

4.1 车辆动力学模型 注1&#xff1a;运动学模型和动力学模型最大的不同点在于 运动学模型是在我们不考虑车辆的受力情况下建立的&#xff08;回顾我们推导出运动学模型的过程&#xff0c;我们没有使用到任何车辆所受的外力作为公式中的已知量&#xff0c;而是直接通过 “ 车速…

力扣173题:二叉搜索树迭代器(含模拟面试)

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容&#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣&#xff01; 推荐&#xff1a;数据分析螺丝钉的首页 关注微信公众号 数据分析螺丝钉 免费领取价值万元的python/java/商业…

OBS实现多路并发推流

OBS实现多路并发推流 解决方案速览相关依赖下载安装多路推流 解决方案速览 利用OBS进行本地直播画面的构建。 使用Multiple RTMP outputs plugin进行多路并发推流。 相关依赖下载安装 OBS软件 # OBS官网 https://obsproject.com/zh-cnMultiple RTMP outputs plugin # 插件官网…

【TB作品】MSP430 G2553 单片机口袋板,流水灯,按键改变花型

功能 按键修改流水灯的花型&#xff0c;一共四种花型。 效果 部分代码 while (1){PinIN();I2C_IODect(); /*按键检测处理 */delay_ms(20);time;if (time > 6){time 0;if (mode 0){index;if (index > 7){index 0;}PinOUT(0, 1); /* 指定0号管脚输出为0 */PinOUT(1, 1)…

视觉盛宴:探索大屏UI设计的卓越美学

视觉盛宴&#xff1a;探索大屏UI设计的卓越美学 在数字时代&#xff0c;用户界面&#xff08;UI&#xff09;设计不仅仅是功能性的体现&#xff0c;更是美学与技术融合的艺术。大屏UI设计&#xff0c;以其独特的视觉冲击力和交互体验&#xff0c;为用户带来了前所未有的视觉盛…

【Web API DOM03】事件监听

一&#xff1a;什么是事件监听 指程序检测有无某一事件发生&#xff0c;如果发生&#xff0c;就调用一个函数做出反应&#xff1b;也称为绑定事件或注册事件 比如鼠标经过显示下拉菜单、点击侧边栏播放轮播图 二&#xff1a;怎么用事件监听 1 语法规范&#xff1a; 元素对…

node.js安装步骤

系统重装node.js&#xff0c;记录一下步骤。 我的项目使用的版本是v14.13.0&#xff0c;到官网下载一下二进制压缩包。 下载完成后&#xff0c;解压压缩包到自己想要的路径。然后进行环境变量设置。 经过这两步以后&#xff0c;使用控制台就可以查看node的版本了。

随心笔记,第五更

目录 脚本代码 启动方式 开机自启 1、打开“任务计划程序”&#xff1a; 2、创建基本任务&#xff1a; 3、触发任务&#xff1a; 4、执行任务&#xff1a; 5、编辑任务&#xff1a; 6、完成设置&#xff1a; 手动启动 示例代码&#xff08;Python脚本自启&#xff0…

算法每日一题(python,2024.06.02)

题目来源&#xff1a;&#xff08;力扣. - 力扣&#xff08;LeetCode&#xff09;&#xff0c;简单&#xff09; 解题思路&#xff1a; 用lower()函数转换为小写&#xff08;也可以用upper()函数全部变为大写&#xff09;&#xff0c;用isalnum()函数去除非字母数字字符&#…

【Linux】进程(3):运行,阻塞,挂起

大家好&#xff0c;我是苏貝&#xff0c;本篇博客带大家了解Linux进程&#xff08;3&#xff09;&#xff0c;如果你觉得我写的还不错的话&#xff0c;可以给我一个赞&#x1f44d;吗&#xff0c;感谢❤️ 目录 &#xff08;A&#xff09; 运行&#xff08;R&#xff09;进程切…

Java | Leetcode Java题解之第127题单词接龙

题目&#xff1a; 题解&#xff1a; class Solution {Map<String, Integer> wordId new HashMap<String, Integer>();List<List<Integer>> edge new ArrayList<List<Integer>>();int nodeNum 0;public int ladderLength(String beginW…

计算机网络学习实践:配置主机通过DHCP获取IP并通过域名访问web服务器

计算机网络学习实践&#xff1a;配置主机通过DHCP获取IP并通过域名访问web服务器 点一点就能配置&#xff0c;不需要输入命令 1.实验准备 实验环境&#xff1a;思科的模拟器 实验设备&#xff1a; 3个服务器&#xff0c;1个二层交换机&#xff08;不是三层的&#xff09;&a…

ctfshow-web入门-信息搜集(web11-web20)

目录 1、web11 2、web12 3、web13 4、web14 5、web15 6、web16 7、web17 8、web18 9、web19 10、web20 1、web11 域名其实也可以隐藏信息&#xff0c;比如flag.ctfshow.com 就隐藏了一条信息 查询域名的 DNS 记录&#xff0c;类型为 TXT&#xff08;域名的说明&#…

20、matlab信号波形生成:狄利克雷函数、高斯脉冲和高斯脉冲序列

1、狄利克雷函数生成波形diric()函数 语法&#xff1a;y diric(x,n) 返回n次的狄利克雷函数对输入数组x的元素求值。 1&#xff09;diric()函数 代码 x linspace(-2*pi,2*pi,301);%定义x取值 d6 diric(x,6); d7 diric(x,7); subplot(2,1,1) plot(x,d6) ylabel(n 6) tit…

YOLOv10:实时端到端目标检测的新突破

目标检测作为计算机视觉领域的一个核心问题&#xff0c;其关键在于能够在图像中准确识别并定位对象。随着深度学习技术的发展&#xff0c;基于深度神经网络的目标检测方法不断涌现&#xff0c;其中YOLO&#xff08;You Only Look Once&#xff09;系列算法以其优异的实时性和准…