【kuangbin计划】简单DP(1-3题 java/c++双语言详细解析)

article/2024/7/13 12:43:46

本意是同时提供java以及c++两种语言的代码的题解

但是无奈oj网站一直欺负java语言慢, 因此本篇题解部分java代码只提供思路参考

不提供语言优化,有兴趣的同学可以自行优化java版本

过不了的java语言均已注明!

目录

4546. 最大和加强加强版 - 线性dp

java版 - 这个vjudge过不了 acw可以过

c++版

4547. 伊格内修斯和公主IV - 摩尔投票法

java版 - 超时tle 只提供思路

c++版 

4548. 猴子和香蕉 - 二维最长上升子序列dp


4546. 最大和加强加强版 - 线性dp

4546. 最大和加强加强版 - AcWing题库

题目:

思路:

定义 f[i][j][k] :前 i 个数,构成 j 个组,且第 i 个数是否在第 j 个组(0/1表示是否存在)

属性:最大值max

状态划分:

(1)选择第i个数

  • 第 i 个数在新开的组(前i-1个数已经构成j-1组)
  • f[i][j][1] = max( f[i-1][j-1][0],f[i-1][j-1][0] )+ w[i]
  • 第 i 个数在旧组(前i-1个数已经构成j组)
  • f[i][j][1] = max( f[i][j][1],f[i-1][j][1]+w[i] )

(2)不选择第i个数

  • f[i][j][0] = max( f[i-1][j][0],f[i-1][j][1] )

根据状态定义知答案为max(f[n][m][0],f[n][m][1])

因为i只与i-1层有关,所以可以进行优化&1

java版 - 这个vjudge过不了 acw可以过

import java.util.*;class Main
{static int N=1000010,M=1010;static long[][][] f=new long[2][M][2]; //f[i][j][k]前i个数,分成j组,第i个数是否在第j组(0/1表示)static int[] w=new int[N];public static void main(String[] args){Scanner sc=new Scanner(System.in);while(sc.hasNextLine()){String[] s=sc.nextLine().split(" ");int m=Integer.parseInt(s[0]);int n=Integer.parseInt(s[1]);int cnt=2;for(int i=1;i<=n;i++) w[i]=Integer.parseInt(s[cnt++]);for(int i=0;i<2;i++)for(int j=0;j<M;j++) Arrays.fill(f[i][j],-0x3f3f3f3f);f[0&1][0][0]=0;for(int i=1;i<=n;i++){f[i&1][0][0]=0;for(int j=1;j<=m;j++){//选择第i个数且第i个数在新开的组j (前i-1个数已经凑成j-1组)f[i&1][j][1]=Math.max(f[i-1&1][j-1][1],f[i-1&1][j-1][0])+w[i];//选择第i个数且第i个数插在旧组j最后 (前i-1个数已经凑成j组)f[i&1][j][1]=Math.max(f[i&1][j][1],f[i-1&1][j][1]+w[i]);//不选择第i个数 (前i-1个数已经凑成j组)f[i&1][j][0]=Math.max(f[i-1&1][j][1],f[i-1&1][j][0]);}}System.out.println(Math.max(f[n&1][m][0],f[n&1][m][1]));}}}

c++版

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
using namespace std;
#define int long long
#define max(a,b) (a>b?a:b)
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N=1e6+10,M=1010;
int f[2][M][2];
int w[N];
int n,m;signed main()
{io;while(cin>>m>>n){for(int i=1;i<=n;i++) cin>>w[i];memset(f,-0x7f,sizeof f);f[0][0][0]=0;for(int i=1;i<=n;i++){f[i&1][0][0]=0;for(int j=1;j<=m;j++){f[i&1][j][1]=max(f[i-1&1][j-1][0],f[i-1&1][j-1][1])+w[i];f[i&1][j][1]=max(f[i&1][j][1],f[i-1&1][j][1]+w[i]);f[i&1][j][0]=max(f[i-1&1][j][1],f[i-1&1][j][0]);}}cout<<max(f[n&1][m][0],f[n&1][m][1])<<endl;}
}

4547. 伊格内修斯和公主IV - 摩尔投票法

4547. 伊格内修斯和公主IV - AcWing题库

题目:

思路: 

摩尔投票法的经典应用

如果有一个数x出现次数超过一半,则通过1v1打擂台的方式

与和x不同的数两两抵消后仍然存在

原因是因为x超过一半,其他数和它同归于尽后,最后生存下来的绝对是x

java版 - 超时tle 只提供思路

import java.util.*;class Main
{public static void main(String[] args){Scanner sc=new Scanner(System.in);while(sc.hasNext()){int num=0,res=0;int n=sc.nextInt();while(n-->0){int cur=sc.nextInt();if(res==0) //第一个人当擂主{res=cur;num=1;}else if(cur!=res){num--; //同归于尽if(num==0) //如果擂主挂了 换新擂主{res=cur;num=1;}}else num++;}System.out.println(res);}}
}

c++版 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
using namespace std;
#define int long long
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)signed main()
{io;int n;while(cin>>n){int num=0,res=0;while(n--){int cur;cin>>cur;if(!res) //第一个直接当擂主{res=cur;num=1;}else if(res!=cur){num--; //与挑战者同归于尽if(!num) res=cur,num=1; //如果擂主挂了换新擂主}else num++;}cout<<res<<endl;}
}

 

4548. 猴子和香蕉 - 二维最长上升子序列dp

4548. 猴子和香蕉 - AcWing题库

题目:

思路:

f[i]:前i个积木能堆起来的最大高度

先将每组数据的长宽高能摆放的所有情况存入数组

2种朝向×3种底面=6种摆放情况

按长宽从小到大排序,寻找满足 " 长和宽均递增 " 的最长上升子序列长度

不熟悉最长上升子序列dp模板的同学,可以学习一下:

【蓝桥杯集训26】线性DP(4 / 4)_Roye_ack的博客-CSDN博客

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <deque>
using namespace std;
//#define int long long
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N=31*6; //一共n组数据 每组数据有2种朝向和3种底面
int f[N]; //f[i]表示前i个积木堆叠的最大高度
int n,m;typedef struct 
{int x,y,z;
}cube;bool cmp(cube a,cube b)
{if(a.x!=b.x) return a.x<b.x;return a.y<b.y;
}signed main()
{io;int cnt=0;cube a[N];while(cin>>n&&n){cnt++;for(int i=1;i<=n;i++){int x,y,z;cin>>x>>y>>z;a[i].x=x,a[i].y=y,a[i].z=z;a[i+n].x=x,a[i+n].y=z,a[i+n].z=y;a[i+2*n].x=y,a[i+2*n].y=x,a[i+2*n].z=z;a[i+3*n].x=y,a[i+3*n].y=z,a[i+3*n].z=x;a[i+4*n].x=z,a[i+4*n].y=x,a[i+4*n].z=y;a[i+5*n].x=z,a[i+5*n].y=y,a[i+5*n].z=x;f[i]=0;}sort(a+1,a+1+n*6,cmp); //按长和宽从小到大排序int res=0;for(int i=1;i<=n*6;i++){f[i]=a[i].z;for(int j=1;j<i;j++)if(a[i].x>a[j].x&&a[i].y>a[j].y)f[i]=max(f[i],f[j]+a[i].z);res=max(res,f[i]);}cout<<"Case "<<cnt<<": maximum height = "<<res<<endl;}
}


http://www.ngui.cc/article/show-1007534.html

相关文章

双重检查锁定与延迟优化

双重检查锁定与延迟优化1. 双重所检查的由来2. 问题根源3. 基于volatile的解决方案4. 基于类初始化的解决方案在Java多线程程序中&#xff0c;有时需要采用延迟初始化来降低初始化类和创建对象的开销。双重检查锁定是常见的延迟初始化技术&#xff0c;但它是一个错误的用法。本…

STM32-9 STM32CubeMX的使用方法

一、 说明 本项目是基于FreeRTOS项目的STM32CubeMX开发方式&#xff0c;说明了具体配置与相关参数&#xff0c;以及mdk使用&#xff0c;裸机也可以参考本配置。 二、项目建立步骤 1、新建项目 2、选择芯片型号 3、配置时钟 RCC 设置&#xff0c;选择 HSE(外部高速时钟) 和L…

Baumer工业相机堡盟相机在BGAPI SDK中如何实现Bitmap的复制克隆(C#)

项目场景 Baumer工业相机堡盟相机是一种高性能、高质量的工业相机&#xff0c;可用于各种应用场景&#xff0c;如物体检测、计数和识别、运动分析和图像处理。 Baumer的万兆网相机拥有出色的图像处理性能&#xff0c;可以实时传输高分辨率图像。此外&#xff0c;该相机还具…

Go map 内存泄露

前言 在Go中, map这个结构使用的频率还是比较高的. 其实在所有的语言中, map使用的频率都是很高的. 之前在使用中, 一直都知道map的内存在元素删除的时候不会回收, 但一直没有仔细的研究为什么. 今天就来好好揣摩揣摩. func main() {m : make(map[int][128]byte)for i : 0; …

Python参数类型定义、私有函数与变量、全局变量

函数的参数类型定义 参数名 冒号 类型函数函数定义在Python3.7之后可用函数不会对参数类型进行验证 def add(a:int, b:int3):print(a b)add(1, 2) add(hello, xiaomu)def test(a:int, b:int3, *args:int, **kwargs):print(a, b, args, kwargs)test(1, 2, 3, 4, namexiaomu)…

用户态--fork函数创建进程

我们一般使用Shell命令行来启动一个程序&#xff0c;其中首先是创建一个子进程。但是由于Shell命令行程序比较复杂&#xff0c;为了便于理解&#xff0c;我们简化了Shell命令行程序&#xff0c;用如下一小段代码来看怎样在用户态创建一个子进程。 #include <stdio.h> #i…

OceanBase CTO杨传辉:持续降低使用门槛,打造开发者友好的分布式数据库

3月25日&#xff0c;首届OceanBase开发者大会在北京举行。大会发布了OceanBase 4.1版本&#xff0c;公布两大友好工具&#xff0c;升级文档易用性&#xff0c;统一企业版和社区版代码分支&#xff0c;全面呈现了OceanBase打造极致的开发者友好数据库的成果。过去13年&#xff0…

【广州华锐互动】电力线路检测VR实训系统有哪些特色?

在电力系统运行中&#xff0c;故障测试是非常重要的一环&#xff0c;旨在检测和排除系统中可能存在的故障&#xff0c;保障电力系统的正常运行。传统的故障测试方法往往需要在实际场景下进行操作&#xff0c;不仅操作难度较大&#xff0c;而且存在安全隐患&#xff0c;同时操作…

详解内核态与用户态

介绍下内核态与用户态 内核态和用户态是操作系统中的两种不同的运行状态&#xff0c;它们的区别如下&#xff1a; 权限不同&#xff1a;内核态是操作系统拥有最高权限的运行状态&#xff0c;可以访问系统的所有资源&#xff0c;而用户态只能访问受限的资源。 系统调用&#x…

网易云音乐API部署Vercel获取接口过程

前提&#xff1a;部署自己的网易云接口主要用途在于在完成前端的仿网易云播放器的时候&#xff0c;根据自己部署的接口可以用于获取数据。大体流程是通过在github上fork别人的API接口项目&#xff0c;然后在Vercel部署即可获得自己的网易云后端数据接口了&#xff0c;不过根据我…