站长工具

[ABC270D] Stones

作者：ybtarr

[ABC270D] Stones

题意

有两个人玩游戏，有 \(n\) 个石子，和一个长度为 \(k\) 的序列，每次可以取 \(a_i\) 个但前提是剩下来的石子数有 \(a_i\) 个，第一个人先取，问两边都是用最优策略时，第一个人最多能得多少个石子。

思路

可以设计状态 \((x, y, f)\) 表示第一个人取了 \(x\) 个石子，第二个人取了 \(y\) 个石子，由第 \(f + 1\) 人开取，显然 \(x + y \le n\)。

那么可以优化状态，因为要求的是第一个人最多能得多少个石子，所以可以将其中一个变量提取出来变成最优属性，可是光靠知道另一个人取了多少个石子是不够的，所以可以将它变成一共已经取了 \(x\) 个石子，还有由于两个人都用的是最优策略，所以 \(f\) 可以优化掉，也就变成了 \(dp_x = y\)，那转移就是 \(dp_x = \max(x - dp_{x - a_i})\)。

代码

#include <iostream>

using namespace std;

const int MaxN = 110, MaxV = 1e4 + 10;

int dp[MaxV], a[MaxN], n, k;

int main() {
  cin >> n >> k;
  for (int i = 1; i <= k; i++) {
    cin >> a[i];
  }
  for (int i = 0; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      if (i >= a[j]) {
        dp[i] = max(dp[i], i - dp[i - a[j]]);
      }
    }
  }
  cout << dp[n] << endl;
  return 0;
}
本文转载于网络 如有侵权请联系删除

相关文章

  • 从零开始学习UCOSII操作系统12–内存管理

    大家好，又见面了，我是你们的朋友全栈君。从零开始学习UCOSII操作系统12–内存管理前言： 在标准的C语言中，可以用malloc()和free()2个动态的分配内存和 释放内存，但是在嵌入式中，调用malloc()和free()却是非常危险的。 因为多次调用这两个函数，会把原来的很大的一块连续的内存区域逐渐的分割成许多非常小的而且彼此又不相邻的内存块，也就是所谓的内存碎片。这样子的话，使得程序后面连一段非常小的内存都分配不到，另外由于内存管理算法上的原因，malloc()和free()函数执行的时间是不确定的。1、分区的概念：操作系统把连续的大块内存按分区来管理，每个分区中包含整数个大小相同的内存块，利用这种机制，UCOSII对malloc和free函数进行了改进。使得他们可以得到和释放固定的大小的内存块。这样子malloc和free函数的执行时间就是确定的了。（为什么？）函数原型：void*malloc(unsignedintnum_bytes); //分配长度为NUM_BYTES字节的内存块。返回值是void指针，void*表示未确定的类型的指针，明确说明，这个函数仅仅只是为了申

  • 文件上传下载工具类

    文件上传application.properties文件设置（默认设置1MB） #设置上传文件的大小 spring.servlet.multipart.max-file-size=100MB spring.servlet.multipart.maxRequestSize=100MB publicStringuploadFile(@RequestParam("file")MultipartFilefile)throwsException{ if(file==null||file.isEmpty()){ thrownewException("未选择需上传的文件"); } StringfilePath=newFile("./apiFile").getAbsolutePath(); FilefileUpload=newFile(filePath); if(!fileUpload.exists()){ fileUpload.mkdirs(); } StringfileName=serviceUuid+file.getOriginal

  • WordPress 4.9“Tipton”正式版已于11月14号正式发布

    说起博客开源程序，我想很多人都会想到wp，它是一种使用PHP语言开发的博客平台，用户可以在支持PHP和MySQL数据库的服务器上架设属于自己的网站，当然如果你的技术很牛掰也可以把它当作一个内容管理系统（CMS）来使用。11月14号WordPress开发团队发布了WordPress4.9正式版，为了纪念爵士音乐家和乐队领袖BillyTiptonWordPress4.9命名为Tipton。但是针对国内使用wp并不如zb（Z-blog）顺手，因为zb是国人开发的，功能和界面更加使我们本土的博主们，像月光和卢松松都是采用zb的开源程序的，有点跑题了啊，说回此次wp的更新吧，WordPress4.9增加了代码错误检查功能，保证网站不出错。自定义面板中增加了设计草稿，定期发布，以及锁定，预览等功能，让内容创建者可以更好地进行协同工作。此外，代码语法高亮显示和错误检查功能，会给你一个简洁、流畅的建站体验。最后，该版本还增加了一个很赞的相册小工具，并改进了主题的浏览和切换体验。自定义工作流程改进网站设计自定义的草稿和定期发布是的，你没看错。就像你起草和修改文章，并安排网站按照选择的日期和时间进行发布一

  • 我用90年代的古董电脑训练CNN

    杨净发自凹非寺 量子位报道|公众号QbitAI在90年代的电脑上实现CNN是一种什么体验？最近，一位日本小哥武田广正（音译）就在1990年的电脑PC-9801上实现了CNN来识别手写字符。就像这样。可能因为电脑性能的限制，整个识别过程要消耗一分多钟。原来30年前CNN是这样实现的。他还将整个过程分享到了推特上，得到了大量的关注。不少网友惊叹之余，还表示，心疼这个电脑，学习AI一定很难……如何实现？虽然目前这项技术还没有开源，但早在93年就已经有人将CNN玩得很溜了。这个人就是LeCun。前不久，一段关于LeCun93年的视频火了。视频中展现的是，当时的文字识别系统已经用上了CNN。他首先是电脑的系统中编写了一种网络数据结构的编译器，并生成了可编译的C语言代码，在源代码中以权重和网表（netlist）代表文字。整套系统是在算力为20MFLOPS的DSP版上运行。当时，手写数字数据集MNIST还没有问世，LeCun则用摄像拍摄来构建文字识别系统的。除此之外，还需要解决文字缩放、位置等问题。只需在纸上写好任意数字，不管任意大小形状，或者带有一定的“艺术性”，只要用摄像头导入电脑，就可以识别。

  • 七层网络协议

    　　在前一篇博客运维往事一次负载均衡坏点检测事故中我提到了在生产环境中在第四层和第七层做healthCheck，这个第四层和第七层到底是什么意思呢？除了第四层第七层之外，其他的几层到底是什么？这几层到底做了啥？ 　　OSI把整个网络分为7层，但tcp/ip只分为4层，osi的七层从上到下分别是应用层,表示层,会话层传输层,网络层,数据链路层,物理层，如下图。 　但是TCP/IP有不同的分层模型，分别为应用层，传输层，网络层，网络接口层 　其实就是讲OSI中的应用层表示层会话层统称为应用层，或者是将数据链路层和网络层通称为网络接口层。接下来我们就以OSI7层模型为例，来简单说下网络协议。为什么选7层而不是4层，我觉得划分越详细越容易理解其中的细节。这估计也是为什么将网络分层的原因。应用层　　我们先从离大多数人最近的一层开始，这也是大多数人能接触到的一层。应用层最关注的起始是数据的用途，比如应用层常见的协议__httphttpsftpsshsocks……__。应用参的协议都是给用户提供某种功能，其实还是封装了下层的网络协议。表示层　　我觉得表示层和会话层这两层被强制从应用层划分出来还

  • Win10 WSL + Linux 开源 EDA（二）

    Win10WSL+Linux开源EDA（一）上一篇我们在一台Win10家庭版电脑上安装了WSL2的Ubuntu16.04LTS，这篇我们将安装一款开源的Verilog仿真器，EpicSim。说到开源Verilog仿真器，最知名的就是IcarusVerilog[http://iverilog.icarus.com/]了（简称iVerilog）。EpicSim就是基于iVerilog进行了针对性的优化，使其在RTL设计（的仿真）上可以有2倍以上的性能提升，并且充实了对Verilog语言的支持，大幅提高了iVerilog对场景的适应性。开发团队（芯华章）在对iVerilog进行优化和改造的同时，对其仿真精度上的实现方式进行了修复和校准，使其结果与现有商用软件保持一致。(source,http://edagit.com/)文末的原文链接指向了EpicSim开源社区的网站EDAGit，感兴趣的朋友可以去做深入了解。开始EpicSim的安装吧，我们先在/mnt/d下面新建一个目录作为该项目的工作目录，例如/mnt/d/wsl2。正式安装EpicSim之前，还需要先安装一些编译EpicSim所需要的

  • 重学计算机组成原理(十二) - 异常和中断

    1概览完好的程序都满足以下特征自动运行 我们的程序和指令都是一条条顺序执行，不需要通过键盘或者网络给这个程序任何输入 正常运行 没有遇到计算溢出之类的程序错误。 不过，现实的软件世界可没有这么简单程序不仅是简单的执行指令，更多的还需要和外部的输入输出打交道程序在执行过程中，还会遇到各种异常情况，比如除以0、溢出，甚至我们自己也可以让程序抛出异常。遇到这些情况，计算机是怎么运转的呢，也就是说，计算机究竟是如何处理异常的2异常:硬件、系统和应用的组合拳2.1软件还是硬件异常?一提到异常(Exception)，可能你的第一反应就是Java中的Exception。不过我们今天讲的，并不是这些软件开发过程中遇到的“软件异常” 而是和硬件、系统相关的“硬件异常”。当然，“软件异常”和“硬件异常”并不是业界使用的专有名词，只是我为了方便给你说明，和Java中软件抛出的Exception进行的人为区分，你明白这个意思就好。尽管，这里我把这些硬件和系统相关的异常，叫作“硬件异常”。但是，实际上，这些异常，既有来自硬件的，也有来自软件层面的。比如，我们在硬件层面 当加法器进行两个数相加的时候，会遇到算术溢

  • 腾讯视频P2P带宽节省率持续提升之路

    要想提升P2P带宽节省率，最直接的方式当然是压缩CDN带宽，但简单粗暴的减少CDN下载势必会带来播放体验问题。腾讯视频数据传输研发高级工程师严华梁在LiveVideoStackCon2019深圳的演讲中详细介绍了腾讯视频针对P2P带宽节省的最新探索与实践。文/严华梁整理/LiveVideoStackPART1/P2P技术项目背景P2P实际上是利用用户之间互相分享视频的数据，来减少从CDN下载数据的量，从而达到带宽节省的效果。一般情况下，在使用P2P进行带宽节省的基础上，服务所需带宽的计算公式如上图所示：带宽=播放量平均码率*平均播放时长(1-P2P带宽节省率)。观看视频的用户除了从平台服务器上调用数据，还会从其他用户那里来调用数据。腾讯视频业务在过去几年迎来了高速的发展，用户规模不断提高，无论是播放量还是视频平均码率都有明显的提升。此时摆在我们面前的一大挑战就是：如何持续提升P2P带宽节省率，并做到CDN带宽成本保持较少增长？上图展现了我们提升P2P带宽节省率的思路。结合之前的带宽计算公式我们可知，如果需要降低CDN的带宽成本，最简单粗暴的方式就是减少CDN的下载，但这样会带来诸如卡顿

  • 还看不懂同事代码？快来补一波 Java 7 语法特性

    前言Java平台自出现到目前为止，已经20多个年头了，这20多年间Java也一直作为最流行的程序设计语言之一，不断面临着其他新兴编程语言的挑战与冲击。Java语言是一种静态强类型语言，这样的语言特性可以让Java编译器在编译阶段发现错误，这对于构建出一个稳定安全且健壮的应用来说，尤为重要。但是也因为这种特性，让Java开发似乎变得缺少灵活性，开发某些功能的应用时，代码量可能是其他语言的几倍。Java开发的不足之处也体现越来越复杂的JDK上，越来越复杂的JDK让开发者完全理解的难度变的非常大。以至于开发者有时会重复实现一个JDK中已经提供了的功能。为了跟上互联网应用编程发展的脚步，Java从9版本开始调整了JDK发布的节奏，JDK的每次更新都注重提高生产效率，提高JVM性能，推行模块化等，让开发者可以更多的专注于业务本身，而不是浪费过多的时间在语言特性上。Java语言的更新要在语言的严谨性和灵活性上找到一个平衡点，毕竟灵活性可以减少编码的复杂度，而严谨性是构建复杂且健壮应用的基石。Java7语言特性Java重要的更新版本是在Java5版本，这个版本中增加了如泛型、增强for、自动装箱拆箱

  • Python与Cisco 的事儿之二

    坚持连续Python大战CiscoNetwork。  #!/usr/bin/python  from netmiko import ConnectHandler from netmiko.ssh_exception import NetMikoTimeoutException import time import sys import getpass import re import StringIO class CiscoNetwork():         def __init__(self,username,password):                  self.username = username                  self.password = password         def CiscoDevice(self,iplist):  self.device={'device_type':'cisco_ios',                               'usern

  • 各种 IntelliJ IDEA 酷炫插件推荐

    今天介绍一下IDEA的一些炫酷的插件，IDEA强大的插件库，不仅能给我们带来一些开发的便捷，还能体现我们的与众不同。1.插件的安装打开setting文件选择Plugins选项Ctrl+Alt+SFile->Settingimg分别是安装JetBrains插件，第三方插件，本地已下载的插件包。详情见关于settings的文章。http://www.cnblogs.com/jajian/p/8108690.html2.各种插件1.activate-power-mode和PowermodeII根据Atom的插件activate-power-mode的效果移植到IDEA上img写代码是整个屏幕都在抖动，activate-power-mode是白的的，PowermodeII色彩更酷炫点。2.BackgroundImagePlusidea背景修改插件，让你的idea与众不同，可以设置自己喜欢的图片作为code背景。img安装成功之后重启，菜单栏的VIew标签>点击SetBackgroundImage(没安装插件是没有这个标签的)，在弹框中路由选择到本地图片，点击OK即可。3.Grepc

  • CES 2019进行时| “5G、无线、AI产品”专场：高通、三星、本田、宝马、阿里、百度…

    CES2019，仍如火如荼进行中。VRPinea已连续三日进行跟踪报道。考虑到如今有关5G、无线、AI的讨论十分激烈。今日，我们特意为各位奉上“CES2019|5G、无线、AI专场”。涉及高通、英特尔、三星、本田、宝马，和阿里、百度等诸多知名厂商，及其最前沿科技产品。5G：+VR、芯片、手机、网关近年来，5G已成为科技界竞相追逐的技术焦点。从运营商到手机、芯片厂商，再到无人驾驶、VR/AR等领域，5G相关话题讨论不断。尤其，时值2019年，5G将“跑步”进入大规模商用的特殊时期，作为全球科技盛会的CES2019也不可避免地成为5G之“没有硝烟”的战场。VRHTC：或推出5G外接设备和云VR服务CES2019上推出一大波新品的HTCVive吸足眼球。关于5G和云VR方面，HTC中国区总裁汪丛青、HTCVive产品及策略副总鲍永哲也有相关消息透出：HTC一直在“基于5G的云VR技术”上，有研发投入。未来几个月内，HTC和其他厂商都将有5G相关的原型产品曝光。此外，针对VIVECOSMOS，HTC或最早于今年晚些时候推出一款基于5G网络的外接设备；并于2020年初，推出类似的云VR服务。NO

  • Linux Kernel Cgroups源码浅析

    本文是我几个月前在研究linuxkernelCgroups时整理的。文中大部分的理论知识是从网上各种贴子solo的，源码分析部分，我是基于kernel4.4.19的代码进行解读分析的，各个内核版本之间应该几乎没啥差别。了解内核中Cgroups的知识，对理解docker底层原理还是有帮助的。##介绍Cgroups是controlgroups的缩写，是Linux内核提供的一种可以限制、记录、隔离进程组（processgroups）所使用的物理资源（如：cpu,memory,IO等等）的机制。##Cgroups的功能限制进程组可以使用的资源数量（Resourcelimiting）。比如：memory子系统可以为进程组设定一个memory使用上限，一旦进程组使用的内存达到限额再申请内存，就会出发OOM（outofmemory）。进程组的优先级控制（Prioritization）。比如：可以使用cpu子系统为某个进程组分配特定cpushare。记录进程组使用的资源数量（Accounting）。比如：可以使用cpuacct子系统记录某个进程组使用的cpu时间。进程组隔离（Isolation）。比如

  • 腾讯云文档服务简介

    名称 描述 APPID 开发者访问文档服务时拥有的用户维度唯一资源标识，用以标识资源，可在API密钥管理页面获取 SecretId 开发者拥有的项目身份识别ID，用以身份认证，可在API密钥管理页面获取 SecretKey 开发者拥有的项目身份密钥，可在API密钥管理页面获取 Bucket 存储桶，文档服务中用于存储数据的容器。有关存储桶的进一步说明，请参见存储桶概述文档 Object 对象，文档服务中存储的具体文件，是存储的基本实体 ObjectKey 对象键，对象（Object）在存储桶（Bucket）中的唯一标识。有关对象与对象键的进一步说明，请参见对象概述文档 Region 地域信息，枚举值可参见可用地域文档，例如：ap-beijing、ap-hongkong、eu-frankfurt等 快速入门要使用腾讯云文档服务，需要先执行以下步骤： 在腾讯云数据万象控制台开通腾讯云数据万象服务。 在腾讯云数据万象控制台创建一个存储桶。 在访问管理控制台中的API密钥管理页面里获取APPID、SecretId、SecretKey内容。 编写一个

  • 工作机会

    美团招聘中高级靠谱前端开发，如果想加入美团，可以发简历给我，符合基本条件可以帮助内推简历。 我的邮箱：xxcanghai@gmail.com 邮件标题格式：[简历]姓名-职位 最后记得发我简历的同学在下面留言，如可以推荐我会回复的。 想要招聘需求的直接去https://www.lagou.com/jobs/list_%E7%BE%8E%E5%9B%A2看吧 关于美团：  该有的都会有。 如果您认为本文对得起您所阅读他所花的时间，欢迎点击右下角↘推荐。您的支持是我继续写作最大的动力，谢谢 作者：沧海月明 出处：http://www.cnblogs.com/xxcanghai/ 本文地址：http://www.cnblogs.com/xxcanghai/ 本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

  • Mysql5.6 online ddl

    Innodb性能改善方面： 　　--Userscanaddindexesandperformstandardtablealterationswhilethedatabaseremainsavailableforapplicationupdates。　　支持在线操作（addindex、altertable）： 例子一：在线添加索引：开启一个session，对italk库下的data_userinfo表做创建索引的操作，（该表大概70万数据）：mysql>>createindexidx_groupidondata_userinfo(groupid);QueryOK,0rowsaffected(9.26sec)Records:0Duplicates:0Warnings:0同时在另外一个session中，执行对该表的update操作：mysql>>updatedata_userinfosetstatus=1whereid=22;QueryOK,1rowaffected(0.02sec)Rowsmatched:1Changed:1Warnings:0update操作立即返

  • mysql的安装真不爽

    下载慢，安装慢，最后启动时进程意外终止。为了让程序能适配更多数据库，忍了。

  • 嵌入式入门学习笔记1：资料收集

    一：网上购买的500G资料 资料地址：https://pan.baidu.com/s/1siwOPjtcRCPZNikN4-Z2tw密码：lhnr   二.嵌入式涉及的知识点 1.QT应用的开发 2.系统驱动的安装，以及系统驱动问题的排故 3.Liunx系统的掌握 4.底层硬件的控制 （错了再改吧！）   三：查找重复文件 1.共查出127G的重复资料！   四.常见的嵌入式开发板/学习板 联发科/华为/三星等处理器规格表 4412开发板四核A9嵌入式Android安卓linux2440ARM9迅为ARM开发板 讯为科技 三星4412 上市时间：2012年 树莓派3代B+型RaspberryPi3b+/3b电脑开发板python编程套件     瑞芯微rk3288开发板ARM卡片电脑UbuntuAndroidLinux开源板 北京丽萨科技 使用芯片：RK3288 生产企业：瑞芯微（国内） 上市时间：2014年04月 立萨科技三星开发板A9四核S5P4418开发板安

  • promise

    promise是什么？ 1、主要用于异步计算 2、可以将异步操作队列化，按照期望的顺序执行，返回符合预期的结果 3、可以在对象之间传递和操作promise，帮助我们处理队列 为什么会有promise？ 为了避免界面冻结（任务） 同步：假设你去了一家饭店，找个位置，叫来服务员，这个时候服务员对你说，对不起我是“同步”服务员，我要服务完这张桌子才能招呼你。那桌客人明明已经吃上了，你只是想要个菜单，这么小的动作，服务员却要你等到别人的一个大动作完成之后，才能再来招呼你，这个便是同步的问题：也就是“顺序交付的工作1234，必须按照1234的顺序完成”。 异步：则是将耗时很长的A交付的工作交给系统之后，就去继续做B交付的工作，。等到系统完成了前面的工作之后，再通过回调或者事件，继续做A剩下的工作。 AB工作的完成顺序，和交付他们的时间顺序无关，所以叫“异步”。 异步操作的常见语法 事件监听 document.getElementById('#start').addEventListener('click',start,false); functionstart(){

  • 宕机了，Redis数据丢了怎么办？

    持续原创输出,点击上方蓝字关注我 目录 前言什么是AOF？ 三种写回策略日志文件太大怎么办？AOF重写会阻塞主线程吗？AOF的缺点总结 什么是RDB？ 给哪些数据做快照？快照时能够修改数据吗？多久做一次快照？增量快照AOF和RDB混合使用总结 总结 前言 Redis作为内存型的数据库，虽然很快，依然有着很大的隐患，一旦「服务器宕机」重启，内存中数据还会存在吗？ 很容易想到的一个方案是从后台数据恢复这些数据，如果数据量很小，这倒是一个可行的方案。但是如果数据量过大，频繁的从后台数据库访问数据，压力很大；另外一方面恢复数据的时间极慢。 对于Redis来说，实现数据的持久化和快速恢复是至关重要。 今天这篇文章就来介绍一下Redis持久化的两种机制AOF日志、RDB快照。 什么是AOF日志？ AOF(AppendOnlyFile)日志称之为「写后日志」，即是命令先执行完成，把数据写入内存，然后才会记录日志。 AOF日志（文本形式）会将收到每一条的命令且执行成功的命令以一定的格式写入到文本中（追加的方式）。 「写后日志有什么好处呢？」如下： 对于写前日志无论命令是否执行成功都会被记录，

  • 使用阿里云服务器ECS搭建Linux（centos 8.2）

    有一段时间没有使用，再登录阿里云的页面，又有变化了，找了好一会才找到地方?‍♀️以现在的页面为例记录一下搭建环境的步骤。 1.进入阿里云首页，登录后点击控制台。  2.点击左侧菜单，选择云服务器ECS。  3.点击实例，进入实例列表，如果第一次使用需要创建实例，如果要修改实例的配置则点击管理。 4.如果服务器还在运行，先停止掉，再点击更多-更换操作系统，然后点击确定。 5.选择公共镜像➡️选择CentOS版本，这里我们选择的是8.264位，登录名默认root。设置登录密码,勾选协议，点击确认订单。如果你的阿里云账号绑定了手机，这里需要手机验证码，验证后提示更换成功。   6.点击管理控制台返回，等待实例重启，启动成功后点击远程链接。点击立即登录。   7.登录后，可以看到实例id，且输入命令ll能够看到如下目录。此时centos环境搭建成功。  

相关推荐

推荐阅读