当前位置: 首页 > news >正文

ACW石子合并-XMUOJ元素共鸣:唤醒神之眼 -区间DP

题目

思路

话不多说,直接上代码

代码

/*
ACW石子合并-XMUOJ元素共鸣:唤醒神之眼 
JinlongW-2024/05/25 
区间DP
当i<j时,f[i][j]=min(f[i][k]+f[k][j]+s[j]-s[i-1])
当i=j时,f[i][j]=0
最终答案:f[1][n] 
*//*
区间DP模板:
所有的区间dp问题枚举时,第一维通常是枚举区间长度,并且一般 len = 1 时用来初始化,枚举从 len = 2 开始;
第二维枚举起点 i (右端点 j 自动获得,j = i + len - 1)
for (int len = 1; len <= n; len++) {         // 区间长度for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点int j = i + len - 1;                 // 区间终点if (len == 1) {dp[i][j] = 初始值continue;}for (int k = i; k < j; k++) {        // 枚举分割点,构造状态转移方程dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);}}
} 
*/
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=310;
int s[N],a[N];
int f[N][N];
int n;
int main(){cin >> n ;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}memset(f,0x3f,sizeof f);for (int len=1;len<=n;len++){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++){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;
}

相关文章:

ACW石子合并-XMUOJ元素共鸣:唤醒神之眼 -区间DP

题目 思路 话不多说&#xff0c;直接上代码 代码 /* ACW石子合并-XMUOJ元素共鸣&#xff1a;唤醒神之眼 JinlongW-2024/05/25 区间DP 当i<j时&#xff0c;f[i][j]min(f[i][k]f[k][j]s[j]-s[i-1]) 当ij时&#xff0c;f[i][j]0 最终答案&#xff1a;f[1][n] *//* 区间DP…...

大语言模型实战——搭建纯本地迷你版RAG

1. 概念 RAG&#xff08;Retrieval Augmented Generation&#xff09;检索增强生成&#xff0c;它结合了搜索技术和大语言模型的提示词功能&#xff0c;以搜索算法找到的信息作为背景上下文&#xff0c;来辅助大语言模型&#xff08;Large Language Model, LLM&#xff09;生成…...

内存分配算法

一、实验目的&#xff1a; 实验目的&#xff1a; 通过编写一个内存分配模拟程序&#xff0c;实现首次适应算法&#xff08;First Fit&#xff09;、循环首次适应算法&#xff08;Next Fit&#xff09;、最佳适应算法&#xff08;Best Fit&#xff09;和最差适应算法&#xff08…...

Hive运行错误

Hive 文章目录 Hive错误日志错误SessionHiveMetaStoreClientql.Driver: FAILED: Execution Error, return code 2 from org.apache.hadoop.hive.ql.exec.mr.MapRedTaskerror: Could not find or load main class org.apache.hadoop.mapreduce.v2.app.MRAppMaster Please check …...

vue3之使用图片实现类似于 el-radio 的单选框功能,并且可实现选中和取消选中

背景 我们在工作中常用的一般都是使用类似于 element-plus 中的 el-radio 或者是 el-checkbox 来实现单选或者多选 若有一天我们遇到了一个新的业务需求,需要使用 图片 来实现类似于 el-radio 的功能,并且要求实现第一次点击时处于选中状态,当我们再次点击时处于非选中状态…...

Vue 安装vue

1、官网安装下载安装nodejs 2、安装完成后&#xff0c;通过命令查看版本,可以查看到版本 node -v npm -v 3、安装Vue CLi npm install -g vue/cli 4、创建项目,vue create test 如果遇到报错&#xff1a; ERROR Error: spawn yarn ENOENT Error: spawn yarn ENOENT at ChildP…...

5月30日在线研讨会 | 面向智能网联汽车的产教融合解决方案

随着智能网联汽车技术的快速发展&#xff0c;产业对高素质技术技能人才的需求日益增长。为了促进智能网联汽车行业的健康发展&#xff0c;推动教育链、人才链与产业链、创新链的深度融合&#xff0c;经纬恒润推出产教融合相关方案&#xff0c;旨在通过促进教育链与产业链的深度…...

嵩山为什么称为三水之源

三水指黄河、淮河、济河&#xff0c;这三条河流环绕在嵩山周边。 黄河横亘在嵩山北部&#xff0c;其支流伊洛河从西南方环绕嵩山&#xff0c;然后汇入黄河。济河&#xff0c;古称济水&#xff0c;源自济源王屋山&#xff0c;自身河道在东晋时代被黄河夺占&#xff0c;从此消失。…...

最新文章合集

GitHub宝藏项目&#xff1a;每天一个&#xff0c;让你的技术库增值不停&#xff01; STORM、SuperMemory、Awesome Chinese LLM、AI写作助手、资料搜集、文章生成、视角问题引导、模拟对话策略、内容导入、浏览器插件、资源库、开源微调模型 开发者必看&#xff1a;Linux终端…...

Jmeter预习第1天

Jmeter参数化&#xff08;重点&#xff09; 本质&#xff1a;使用参数的方式来替代脚本中的固定为测试数据 实现方式&#xff1a; 定义变量&#xff08;最基础&#xff09; 文件定义的方式&#xff08;所有测试数据都是固定的情况下[死数据]&#xff0c;eg:注册登录&#xff0…...

Volatile的内存语义

1、volatile的特性 可见性&#xff1a;对一个volatile变量的读&#xff0c;总能够看到任意一个线程对这个volatile变量的写入。 原子性&#xff1a;对任意单个volatile变量的读/写具有原子性&#xff0c;但类似于volatile这种复合操作不具有原子性。 接下来我们用程序验证。…...

Debezium+Kafka:Oracle 11g 数据实时同步至 DolphinDB 解决方案

随着越来越多用户使用 DolphinDB&#xff0c;各式各样的应用场景对 DolphinDB 的数据接入提出了不同的要求。部分用户需要将 Oracle 11g 的数据实时同步到 DolphinDB 中来&#xff0c;以满足在 DolphinDB 中实时使用数据的需求。本篇教程将介绍使用 Debezium 来实时捕获和发布 …...

前端如何在 WebSocket 的请求头中使用标准 HTTP 头携带 Authorization 信息,添加请求头

WebSocket 的请求头(header)中如何携带 authorization...

Java---图书管理系统(练习版)

1.主函数 import book.Book; import book.BookList; import user.AdminUser; import user.NormalUser; import user.User;import java.util.Scanner;public class Main {public static User Login(){//确认你的身份System.out.println("请输如你的名字");Scanner sc…...

ICML2024 定义新隐私保护升级:DP-BITFIT新型微调技术让AI模型学习更安全

DeepVisionary 每日深度学习前沿科技推送&顶会论文分享&#xff0c;与你一起了解前沿深度学习信息&#xff01; 引言&#xff1a;差分隐私在大模型微调中的重要性和挑战 在当今的深度学习领域&#xff0c;大型预训练模型的微调已成为提高各种任务性能的关键技术。然而&am…...

网络空间安全数学基础·整除与同余

主要内容&#xff1a; 整除的基本概念&#xff08;掌握&#xff09; 素数&#xff08;掌握&#xff09; 同余的概念&#xff08;掌握&#xff09; 1.1整除 定义&#xff1a;设a&#xff0c;b是任意两个整数&#xff0c;其中b≠0&#xff0c;如果存在一个整数q&#xff0c;使 …...

同旺科技 FLUKE ADPT 隔离版发布 ---- 说明书

所需设备&#xff1a; 1、FLUKE ADPT 隔离版 内附链接&#xff1b; 应用于&#xff1a;福禄克Fluke 12E / 15BMax / 17B Max / 101 / 106 / 107 应用于&#xff1a;福禄克Fluke 15B / 17B / 18B...

云计算-角色、特性和模型 (Roles, Characteristics, and Models)

角色、特性和模型 (Roles, Characteristics, and Models) 角色和边界 (Roles and Boundaries) 为了识别云计算模型&#xff0c;我们首先需要了解各种参与者的角色和边界。由于云系统通常遵循面向服务的模型&#xff0c;我们需要了解服务提供者和服务订阅者之间的边界。我们将遵…...

介绍一下Hugging Face,这个公司的背景是什么

Hugging Face是一家成立于2016年的人工智能公司&#xff0c;专注于为AI研究人员和开发者提供开源模型库和工具。以下是关于Hugging Face公司的详细背景介绍&#xff1a; 公司历史与创始人&#xff1a; Hugging Face由Clment Delangue、Julien Chaumond和Thomas Wolf三位法国籍…...

【C++高阶(一)】继承

目录 一、继承的概念 1.继承的基本概念 2.继承的定义和语法 3.继承基类成员访问方式的变化 ​编辑 4.总结 二、基类和派生类对象赋值转换 三、继承中的作用域 四、派生类的默认成员函数 1.派生类中的默认构造函数 2.派生类中的拷贝构造函数 3.派生类中的移动构造函数…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...