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

博弈dp,CF 731E - Funny Game

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

731E - Funny Game


二、解题报告

1、思路分析

游戏规则其实就是交替取前缀和

考虑 f(i) 为 某人先手取前 i 个,最终能得到的最大分差

由于每人都是最佳发挥,所以有如下状态转移:

f(i) = acc[i] - max(f(j)),i + 1 <= j < n

为什么呢?

假如A得分为sumA,B得分为sumB

计算f(i) 时候 f(i) = sumA - sumB

那么转移的时候 f(j) = sumB’ - sumA‘

要f(i) - f(j) = sumA'' - sumB''

2、复杂度

时间复杂度: O(N)空间复杂度:O(N)

3、代码详解

 ​
#include <bits/stdc++.h>
// #include <ranges>
// #define DEBUG
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr double eps = 1E-9;void solve() {int n;std::cin >> n;std::vector<int> acc(n);for (int i = 0; i < n; ++ i) {std::cin >> acc[i];;if (i)acc[i] += acc[i - 1];}for (int i = n - 2; i; -- i) {acc[i] = std::max(acc[i + 1], acc[i] - acc[i + 1]);}std::cout << acc[1];
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
} ();int main() {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif     int t = 1;// std::cin >> t;while (t --)solve();return 0;
}

相关文章:

博弈dp,CF 731E - Funny Game

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 731E - Funny Game 二、解题报告 1、思路分析 游戏规则其实就是交替取前缀和 考虑 f(i) 为 某人先手取前 i 个&#xff0c;最终能得到的最大分差 由于每人都是最佳发挥&#xff0c;所以有如下状态转移&am…...

基础知识:深入理解MongoDB、MySQL与Redis的应用与实践

基础知识&#xff1a;深入理解MongoDB、MySQL与Redis的应用与实践 在现代应用开发中&#xff0c;数据库系统的选择对于系统的性能、扩展性和维护性有着至关重要的影响。MongoDB、MySQL 和 Redis 是三种流行的数据库技术&#xff0c;它们各自有着独特的特点和适用场景。本文将详…...

Reids中List类型、Set类型、SortedSet类型的常用指令

List类型&#xff1a; Redis中的List类型与Java中的LinkedList类似&#xff0c;可以看做是一个双向链表结构。既可以支持正向检索和也可以支持反向检索。 特征也与LinkedList类似&#xff1a; 有序元素可以重复插入和删除快查询速度一般 常用来存储一个有序数据&#xff0c…...

K8S Ingress 常用配置

目录 介绍ingress 安装 基本使用请查看域名重定向前后端分离配置默认证书配置指定证书配置白名单配置黑名单配置Annotations 配置ConfigMap 配置 匹配请求头速率限制限制客户端的最大连接数限制每秒钟段并发连接数限制每分钟段并发请求突发访问限制限制传输速度速率限制白名单 …...

【K8S】K8S架构及相关组件

文章目录 1 K8S总体架构2 相关组件2.1 控制面板组件2.2 节点组件2.3 附加组件 写在最后 1 K8S总体架构 K8S&#xff0c;全称Kubernetes&#xff0c;是一个开源的容器部署和管理平台&#xff0c;由Google开发&#xff0c;后捐献给云原生计算基金会&#xff08;CNCF&#xff09;…...

【MATLAB第108期】基于MATLAB的fast、vbsa、dynia、eet、glue、pawn、rsa敏感性分析模型合集(无目标函数)【更新中】

【MATLAB第108期】基于MATLAB的fast、vbsa、dynia、eet、glue、pawn、rsa敏感性分析模型合集&#xff08;无目标函数&#xff09;【更新中】 一、FAST&#xff08;Fourier Amplitude Sensitivity Test&#xff09; FAST&#xff08;Fourier Amplitude Sensitivity Test&#…...

【K8S】为什么需要Kubernetes?

文章目录 1 什么是Kubernetes&#xff1f;2 三种常见的应用部署方式2.1 传统部署2.2 虚拟化部署2.3 容器化部署 3 Kubernetes的特点写在最后 1 什么是Kubernetes&#xff1f; Kubernetes是 一个开源的&#xff0c;用于管理云平台中多个主机上的容器化应用&#xff0c;Kubernet…...

【Linux】Linux中查找字符串中的命令

在Linux中&#xff0c;查找字符串的命令通常使用grep。grep是一个强大的工具&#xff0c;用于在文件中搜索指定模式的字符串。以下是一些基本用法&#xff1a; 1.在文件中查找字符串 grep "字符串" 文件名例如&#xff0c;查找文件example.txt中包含“hello”的行&…...

最新HTML设计搜索表单

设计搜索表单 页眉中包含表单&#xff0c;表单中只需包含label和Input. 实现如下效果&#xff1a;文本框动态变宽效果 代码&#xff1a;6.2.4.设计搜索表单.html <!DOCTYPE html> <html><head><meta charset"utf-8"><title></t…...

JavaScript constructor原型原型继承

constructor 在 JavaScript 中&#xff0c;构造函数是一种特殊的函数&#xff0c;使用 new 关键字来调用&#xff0c;用于创建对象实例。JavaScript 中的构造函数通常通过 function 关键字定义。 例如&#xff1a; function Person(name, age) {this.name name;this.age a…...

使用Python+moviepy保存截取视频画面

一、 使用VideoFileClip对象的的save_frame函数保存截取的第1帧画面 from moviepy.editor import * mvVideoFileClip(/home/Download/leaves.mp4) mv.save_frame(/home/Download/fst.jpg) # 默认保存截取的第1帧画面 二、 使用VideoFileClip对象的的save_frame函数保存截…...

【DOCKER】显示带UI的软件

1. Linux 1.1 宿主机开放X server权限 xhost 1.2 启动容器 docker run -it --rm --privilegedtrue --useru20 --workdir/home/u20 \ -e DISPLAYhost.docker.internal:0 u20:dev1.3 测试 # 安装测试软件 sudo apt-get -y install x11-apps# 显示测试程序 xclock2. Windows …...

Atcoder Beginner Contest 366

传送门 A - Election 2 时间限制&#xff1a;2秒 内存限制&#xff1a;1024MB 分数&#xff1a;100分 问题描述 在 AtCoder 市举行市长选举。候选人是 Takahashi 和 Aoki。 目前有 N 张有效选票投给了这两个候选人&#xff0c;并且计票正在进行中。这里&#xff0…...

【hexo博客问题】

windows下使用gitbash即可使用 其他bash会产生权限问题 npm install失败 $ npm install npm error code ENOENT npm error syscall open npm error path F:\pf_project\blog_pf\package.json npm error errno -4058 npm error enoent Could not read package.json: Error: E…...

用数组模拟栈和队列

栈 先进后出 //stk 表示定义的栈 //tt表示栈顶的下标 int stk[N], tt 0;//在栈顶上加入一个新的元素 stk[ tt] x;//弹出 tt --;//判断栈是否为空 if (tt > 0) 不为空 else empty//取出栈顶 stk[tt];1.题目 给定一个长度为 N 的整数数列&#xff0c;输出每个数左边第一个…...

Django内置后端和自定义后端

【图书介绍】《Django 5企业级Web应用开发实战&#xff08;视频教学版&#xff09;》_django 5企业级web应用开发实战(视频教学版)-CSDN博客 《Django 5企业级Web应用开发实战&#xff08;视频教学版&#xff09;》(王金柱)【摘要 书评 试读】- 京东图书 (jd.com) 5.2.3 内置…...

嵌入式人工智能(OpenCV-基于树莓派的人脸识别与入侵检测)

1、人脸识别 人脸识别是一种技术&#xff0c;通过检测、跟踪和识别人脸上的关键特征&#xff0c;以确认人脸的身份。它通常用于安保系统、身份验证、社交媒体和人机交互等领域。 人脸识别技术的基本原理是先通过图像处理和计算机视觉算法&#xff0c;提取人脸的特征点和特征描…...

如何选择适合的香港云服务器提供商?

稳定性和可靠性 确保提供商有高水平的服务器正常运行时间&#xff0c;并提供可靠的数据备份和恢复选项。 网络速度和延迟 选择能够提供快速和低延迟网络连接的服务商&#xff0c;尤其是对于目标用户位于中国大陆的企业而言。 客户支持 查看提供商是否提供24/7的客户支持&#x…...

安卓Android JAVA校招/实习面试合集:多线程、强软弱虚引用、进程、内存管理、Activity、Fragment......

本人今年&#xff08;2023年&#xff09;参加了很多面试&#xff0c;也有幸拿到了一些大厂的offer&#xff0c;整理了众多面试资料&#xff0c;后续还会分享众多面试资料。 整理成了面试系列&#xff0c;由于时间有限&#xff0c;每天整理一点&#xff0c;后续会陆续分享出来&a…...

Jeecgboot 字典值自动转化:DictAspect类方法改造,支持IPage、List、Object、Map类自动转化,附有源码

改造的是DictAspect类&#xff1a; 原来使用的 parseDictText(Object result)方法&#xff0c;针对返回对象为Result 的IPage的分页列表数据进行动态字典注入&#xff0c;当单个对象查询&#xff0c;列表查询&#xff0c;或者多个数据放到Map中时&#xff0c;就不会自动转化&am…...

Phi-4-mini-reasoning Chainlit用户体验优化:流式响应+打字机动画实现

Phi-4-mini-reasoning Chainlit用户体验优化&#xff1a;流式响应打字机动画实现 1. 项目背景与目标 Phi-4-mini-reasoning 是一个基于合成数据构建的轻量级开源模型&#xff0c;专注于高质量、密集推理的数据处理能力。作为Phi-4模型家族的一员&#xff0c;它支持128K令牌的…...

5分钟搞定!FLUX.2-Klein-9B在ComfyUI中的快速部署与初体验

5分钟搞定&#xff01;FLUX.2-Klein-9B在ComfyUI中的快速部署与初体验 1. 为什么选择FLUX.2-Klein-9B 如果你正在寻找一个既能高质量生成图像&#xff0c;又对中文提示词理解优秀的AI模型&#xff0c;FLUX.2-Klein-9B值得一试。这个模型特别适合需要频繁进行图像编辑的场景&a…...

千问3.5-9B Visio图表智能生成:从文本描述到专业架构图

千问3.5-9B Visio图表智能生成&#xff1a;从文本描述到专业架构图 1. 效果惊艳的智能图表生成 想象一下&#xff0c;你只需要用简单的文字描述系统架构&#xff0c;就能在几分钟内获得专业的Visio图表。千问3.5-9B让这个场景成为现实。这个模型不仅能理解复杂的系统架构描述…...

PyTorch 2.8开源大模型镜像实操:HuggingFace模型本地化API服务封装

PyTorch 2.8开源大模型镜像实操&#xff1a;HuggingFace模型本地化API服务封装 1. 镜像环境概览 1.1 硬件与软件配置 这个基于PyTorch 2.8的深度学习镜像经过RTX 4090D显卡和CUDA 12.4的深度优化&#xff0c;为大型模型推理和训练提供了开箱即用的环境。主要配置包括&#x…...

AI核心概念解析:Agent、Prompt、Skill 及生态关系

&#x1f310; AI核心概念解析&#xff1a;Agent、Prompt、Skill 及生态关系 一、关键名词正确定义与原理 1. Agent&#xff08;智能体&#xff09; 指具备感知—决策—行动闭环能力的自主软件实体。它不是单个模型&#xff0c;而是一个系统架构&#xff1a;接收输入&#x…...

分布式系统CAP理论之如何取舍

在分布式系统中&#xff0c;CAP 理论 是一个基石性、指导性的理论&#xff0c;它告诉我们&#xff1a;在设计分布式系统时&#xff0c;无法同时满足三个核心特性&#xff0c;只能在三者之间做权衡。&#x1f310; 一、CAP 理论的三个字母代表什么&#xff1f;字母含义说明CCons…...

SeqGPT-560M入门指南:Web界面操作+Jupyter调试+API调用三路径并行

SeqGPT-560M入门指南&#xff1a;Web界面操作Jupyter调试API调用三路径并行 1. 从零开始&#xff1a;认识SeqGPT-560M 如果你正在寻找一个开箱即用、能快速处理中文文本分类和信息抽取的AI工具&#xff0c;那么SeqGPT-560M绝对值得你花十分钟了解一下。 简单来说&#xff0c…...

解析器开发的终极革命:为什么Ohm比传统解析器更强大?

解析器开发的终极革命&#xff1a;为什么Ohm比传统解析器更强大&#xff1f; 【免费下载链接】ohm A library and language for building parsers, interpreters, compilers, etc. 项目地址: https://gitcode.com/gh_mirrors/oh/ohm Ohm是一个用于构建解析器、解释器和编…...

别再傻等1000步了!用DDIM在Stable Diffusion里5分钟搞定高质量出图(附详细参数设置)

5分钟极速出图&#xff1a;DDIM采样器在Stable Diffusion中的实战指南 当你在深夜赶稿需要快速生成概念图时&#xff0c;当客户要求半小时内看到10个设计方案时&#xff0c;传统扩散模型缓慢的生成速度往往让人抓狂。别担心&#xff0c;DDIM采样器就是为这种紧急场景而生的利器…...

电子元器件失效分析与预防实战指南

1. 电子元器件失效的底层逻辑剖析 电子元器件失效的本质是材料特性、环境应力与时间因素共同作用的结果。作为一名硬件工程师&#xff0c;我处理过数百例元器件失效案例&#xff0c;发现失效模式往往遵循"应力-损伤-失效"的因果链。理解这个链条&#xff0c;才能从根…...