forked from Lruihao/lruihao.github.io
-
Notifications
You must be signed in to change notification settings - Fork 0
/
TaoTao要吃鸡.html
317 lines (284 loc) · 46 KB
/
TaoTao要吃鸡.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
<!DOCTYPE html><html class="theme-next pisces" lang="zh-CN,en,default"><head><meta name="baidu-site-verification" content="5rEIjow3aW"><meta name="google-site-verification" content="OhdtVOx5uwpZ_mMm0AZJXzw-dY1PPpAAkdavmmQhIL4"><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><script>!function(e,t,o,c,i,a,n){e.DaoVoiceObject=i,e[i]=e[i]||function(){(e[i].q=e[i].q||[]).push(arguments)},e[i].l=1*new Date,a=t.createElement(o),n=t.getElementsByTagName(o)[0],a.async=1,a.src=c,a.charset="utf-8",n.parentNode.insertBefore(a,n)}(window,document,"script",("https:"==document.location.protocol?"https:":"http:")+"//widget.daovoice.io/widget/0f81ff2f.js","daovoice"),daovoice("init",{app_id:"8a6701dd"}),daovoice("update")</script><link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=6.3.0" rel="stylesheet" type="text/css"><link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.3.0"><link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=6.3.0"><link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=6.3.0"><link rel="mask-icon" href="/images/logo.svg?v=6.3.0" color="#222"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",scheme:"Pisces",version:"6.3.0",sidebar:{position:"left",display:"post",offset:12,b2t:!1,scrollpercent:!0,onmobile:!0},fancybox:!0,fastclick:!1,lazyload:!0,tabs:!0,motion:{enable:!1,async:!1,transition:{post_block:"fadeIn",post_header:"slideDownIn",post_body:"slideDownIn",coll_header:"slideLeftIn",sidebar:"slideUpIn"}},algolia:{applicationID:"",apiKey:"",indexName:"",hits:{per_page:10},labels:{input_placeholder:"Search for Posts",hits_empty:"We didn't find any results for the search: ${query}",hits_stats:"${hits} results found in ${time} ms"}}}</script><meta name="description" content="2018年全国多校算法寒假训练营练习比赛（第二场）B(0 1背包变化 特殊处理一个物品)"><meta name="keywords" content="背包问题,Nowcoder"><meta property="og:type" content="article"><meta property="og:title" content="TaoTao要吃鸡"><meta property="og:url" content="https://lruihao.cn/TaoTao要吃鸡.html"><meta property="og:site_name" content="博採眾長"><meta property="og:description" content="2018年全国多校算法寒假训练营练习比赛（第二场）B(0 1背包变化 特殊处理一个物品)"><meta property="og:locale" content="zh-CN"><meta property="og:updated_time" content="2018-07-22T03:52:11.539Z"><meta name="twitter:card" content="summary"><meta name="twitter:title" content="TaoTao要吃鸡"><meta name="twitter:description" content="2018年全国多校算法寒假训练营练习比赛（第二场）B(0 1背包变化 特殊处理一个物品)"><link rel="alternate" href="/atom.xml" title="博採眾長" type="application/atom+xml"><link rel="canonical" href="https://lruihao.cn/TaoTao要吃鸡.html"><script type="text/javascript" id="page.configurations">CONFIG.page={sidebar:""}</script><title>TaoTao要吃鸡 | 博採眾長</title><noscript><style type="text/css">.sidebar-inner,.use-motion .brand,.use-motion .collection-title,.use-motion .comments,.use-motion .menu-item,.use-motion .motion-element,.use-motion .pagination,.use-motion .post-block,.use-motion .post-body,.use-motion .post-header{opacity:initial}.use-motion .logo,.use-motion .site-subtitle,.use-motion .site-title{opacity:initial;top:initial}.logo-line-after i{right:initial}</style></noscript></head><body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-CN"><script type="text/javascript">console.log("\n` @@#``@@@@@@@@@@@@@@@@@@##,` \n` @@#`;@@@@@@@@@@@@@@@@@@@':' \n` @@#`@@@@@@@@@@@@@@@@@@@#+#;` \n` @@#`@@@@@@@@@@@@@@@@@@###@'. \n` @@+.@@@@@@@@@@@@@@@@@@@@@##, \n` @@#,@@@@@@@@@@@@@@@@@@@@@@#, \n` #@#:@@@@@@@@@@@@@@@@@@@@@@@, \n` #@#'@@@@@@@@@@@@@@@@@@@@@@@. \n` +@#;@@@@@@@@@@@@@@@@@@@@@@# \n` `;: ;@#'@@@@@@@@@@@@@@@@@@+'+@' \n` `,,;';'+';'@@+:@@@@@@@@@@@@##@#',.:#; \n,, `` ``..,:;@@#'@@@@@@@@#####@@@@#:`:. \n` `````:++@@@@@@@@@@@@@###@@@@#+,.. \n ``````.#@@@@@@@@@@@@@@#@@@#++#'`` \n` ```.,,:,.`:@@@@@@@@@@@@@###@@@##'.` \n``..`````..,::;+@@@@@@@@@@@@#+`::+##'`. \n` ````.```,@@@@@@@@@@@##;``.,';` ` \n``.;@@@@@@@@@@@@@@@@@@@@@@###;``..`````` \n#@@@@@@@@@@@@@@@@@@@@@@@@##@#;``,``,.`` \n@@@@@@@@@@@@@@@@@@@.`````..``.. +` `:` \n@+''++#####@@#`.@@@``````` ` `,``` `` \n';;;;'+##+'+.`;+@@@,..```` `` :,. \n;::,,:;+#++``,,#@@@'..``````` ,`.`` \n;,,,,...'#.,,..#@@@#,,.`````` .```` \n:,,,,....`,::;''+#@#;,..`````````.`` \n:,,,.....'##++''';:+':,.`..,,...` \n:,,,...#####+'+#@@@'.';+:. ` `` \n;,,.`'####'#,`.`+@@@+'``` `.` \n;,.`#@@@#+:'+++##+@##@,,,,` \n',.#@@###'''';:,.```,+#. \n+,#@@@####;,,..``````````````` `.:,::\n+@@@@###+;,,..`````````````````` `.,\n#@@@##+',,,........`````````````` \n@@@@#+:,,,,`........`````````` \n@@@#+:,,,,.`````.....`````````` `` \n@@##':,......`````....``` ````` ```\n@@@#':,....,..``````..```` ``` ```\n@@@#',....,,,..``````````` ``` ..\n@@@#,.....,,,,.`` ```````` `````` \n@@@+....,,,,,..````````````` `````````` \n@@@:....,,,,.LiRuihao```````` ```````````` \n#@@,....,,,,.Always Be Yourself !````````````\n,##,,...,::,.https://lruihao.cn ` `......``\n,'#,,..,,:::.`````````........`````` `.,,..\n\n您好！\n这里是李瑞豪的个人博客--博採眾長！\n我的主页是 https://ww.lruihao.cn\n\n\n")</script><div class="container sidebar-position-left page-post-detail"><div class="headband"></div><header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="header-inner"><script>function GetRandomNum(e,t){var n=t-e,r=Math.random();return e+Math.round(r*n)}function setSidebarMarginTop(e){return $("#sidebar").css({"margin-top":e})}function getHeaderOffset(){return $(".header-inner").height()+CONFIG.sidebar.offset}window.onload=function(){var e="不怕万人阻挡，只怕自己投降。W你如何回忆，决定你是一个怎样的人。W人生当苦无妨，良人当归即可。W逝者如斯乎，不舍昼夜。W你别出现在我黎明的梦里，我怕我醒来就抱不到你。W心向大佬，披荆斩棘。W兼收并蓄，博采众长。".split("W"),t=e[GetRandomNum(0,e.length-1)];$("#helloTitle").html(t),setSidebarMarginTop(getHeaderOffset())}</script><div class="site-brand-wrapper"><div class="site-meta"><div class="custom-logo-site-title"><a href="/" class="brand" rel="start"><span class="logo-line-before"><i></i></span> <span class="site-title" style="color:#ddd">博採眾長</span> <span class="logo-line-after"><i></i></span></a></div><p></p><p style="color:#555;font-family:STXK" class="site-subtitle" id="helloTitle" itemprop="description"></p><p></p></div><div class="site-nav-toggle"><button aria-label="切换导航栏"><span class="btn-bar"></span> <span class="btn-bar"></span> <span class="btn-bar"></span></button></div></div><nav class="site-nav"><ul id="menu" class="menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i><br>首页</a></li><li class="menu-item menu-item-lead"><a href="/home" rel="section"><i class="menu-item-icon fa fa-fw fa-paper-plane"></i><br>导航</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i><br>分类</a></li><li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i><br>标签</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i><br>归档</a></li><li class="menu-item menu-item-guestbook"><a href="/guestbook/" rel="section"><i class="menu-item-icon fa fa-fw fa-book"></i><br>留言</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i><br>关于</a></li><li class="menu-item menu-item-search"><a href="javascript:;" class="popup-trigger"><i class="menu-item-icon fa fa-search fa-fw"></i><br>搜索</a></li></ul><div class="site-search"><div class="popup search-popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i> </span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"><input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"></div></div></div></nav></div></header><a href="https://github.com/Lruihao/lruihao.github.io" class="github-corner" target="_blank" title="万水千山总是情,给个star行不行！" aria-label="万水千山总是情,给个star行不行！" rel="external nofollow noopener noreferrer"><svg width="80" height="80" viewbox="0 0 250 250" style="fill:#222;color:#fff;position:absolute;top:0;border:0;right:0" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"/><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin:130px 106px" class="octo-arm"/><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"/></svg></a><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article"><div class="post-block"><link itemprop="mainEntityOfPage" href="https://lruihao.cn/TaoTao要吃鸡.html"><span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person"><meta itemprop="name" content="李瑞豪"><meta itemprop="description" content="so far so good"><meta itemprop="image" content="/images/avatar.png"></span><span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization"><meta itemprop="name" content="博採眾長"></span><header class="post-header"><h2 class="post-title" itemprop="name headline">TaoTao要吃鸡</h2><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i> </span><span class="post-meta-item-text">发表于</span> <time title="创建时间：2018-07-22 10:55:21 / 修改时间：11:52:11" itemprop="dateCreated datePublished" datetime="2018-07-22T10:55:21+08:00">2018-07-22</time> </span><span class="post-category"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-folder-o"></i> </span><span class="post-meta-item-text">分类于</span> <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/ACM/" itemprop="url" rel="index"><span itemprop="name">ACM</span></a></span> ， <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/ACM/背包问题/" itemprop="url" rel="index"><span itemprop="name">背包问题</span></a></span> </span><span class="post-comments-count"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-comment-o"></i> </span><a href="/TaoTao要吃鸡.html#comments" itemprop="discussionUrl"><span class="post-meta-item-text">评论数：</span> <span class="post-comments-count valine-comment-count" data-xid="/TaoTao要吃鸡.html" itemprop="commentCount"></span> </a></span><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-eye"></i> 阅读次数： <span class="busuanzi-value" id="busuanzi_value_page_pv"></span> </span><span class="post-meta-divider">|</span> <span title="post.wordcount"><span class="post-meta-item-icon"><i class="fa fa-file-word-o"></i></span>字数： 686</span><div class="post-description">2018年全国多校算法寒假训练营练习比赛（第二场）B(0 1背包变化 特殊处理一个物品)</div></div></header><div class="post-body" itemprop="articleBody"><p>链接：<a href="https://www.nowcoder.com/acm/contest/74/B" rel="external nofollow noopener noreferrer" target="_blank">https://www.nowcoder.com/acm/contest/74/B</a><br>来源：牛客网</p><p>###题目描述</p><p>Taotao的电脑带不动绝地求生，所以taotao只能去玩pc版的荒野行动了，<br>和绝地求生一样，游戏人物本身可以携带一定重量m的物品，装备背包<br>之后可以多携带h（h为0代表没有装备背包）重量的东西。玩了几天<br>taotao发现了一个BUG，当装备背包之后，如果可携带重量没有满，就<br>可以拿一个任意重的东西。（解释看样例）有一天taotao空降到了一个<br>奇怪的岛上，岛上有n件装备，每个装备都有重量Wi和威力值Vi,但taotao<br>不认识这些装备，所以他来求助你，挑选威力最大的装备，帮助他吃鸡。</p><p>###输入描述:<br>本题有多组输入（小于10），当n=0时结束输入。第一行输入n,m,h。n，m，h为整数，并且0<=n,m,h<=100，接下来n行，每行输入第i个物品的物品的重量Wi和威力值Vi。0<=Wi,Vi<=100.</p><p>###输出描述:<br>输出最大威力值，每组输出一行。</p><p>###示例1</p><p>####输入</p><p>3 3 3<br>2 3<br>3 2<br>2 3<br>0</p><p>####输出</p><p>8</p><p>###说明</p><p>可携带的总重量为6，当拿了前两件装备，此时容量为5/6，还可以再拿第三件物品。</p><p>思路：0-1背包的变形题目，h=0的时候为背包的模板，h！=0的时候枚举每一个需要特殊处理的物品再背包<br></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> v[<span class="number">105</span>];</span><br><span class="line"><span class="keyword">int</span> w[<span class="number">105</span>];</span><br><span class="line"><span class="keyword">int</span> n,m,h;</span><br><span class="line"><span class="keyword">int</span> dp[<span class="number">205</span>];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"></span><br><span class="line"> <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n)==<span class="number">1</span>&&n!=<span class="number">0</span>){</span><br><span class="line"></span><br><span class="line"> <span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&m,&h);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++)</span><br><span class="line"></span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&w[i],&v[i]);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span>(h==<span class="number">0</span>){</span><br><span class="line"></span><br><span class="line"> <span class="built_in">memset</span>(dp,<span class="number">0</span>,<span class="keyword">sizeof</span>(dp));</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="comment">//前i个物品</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j=m;j>=w[i];j--) <span class="comment">//枚举背包重量</span></span><br><span class="line"></span><br><span class="line"> dp[j]=max(dp[j],dp[j-w[i]]+v[i]); <span class="comment">//</span></span><br><span class="line"></span><br><span class="line"> sum=dp[m];</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> m+=h</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k<=n;k++) <span class="comment">//枚举可以被剩下的物品</span></span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">memset</span>(dp,<span class="number">0</span>,<span class="keyword">sizeof</span>(dp));</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){ <span class="comment">//前i个物品</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span>(i!=k){</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j=m;j>=w[i];j--) <span class="comment">//枚举背包重量</span></span><br><span class="line"></span><br><span class="line"> dp[j]=max(dp[j],dp[j-w[i]]+v[i]);</span><br><span class="line"></span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> } <span class="comment">//留下来一个重量，即初始化威力为那个重量的威力</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j=m<span class="number">-1</span>;j>=m-w[k];j--) <span class="comment">//枚举背包重量+剩下物品</span></span><br><span class="line"></span><br><span class="line"> dp[m]=max(dp[m],dp[j]+v[k]);</span><br><span class="line"></span><br><span class="line"> <span class="comment">// printf("%d\n",dp[m]);</span></span><br><span class="line"></span><br><span class="line"> sum=max(sum,dp[m]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>,sum);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p></div><div><div style="padding:10px 0;margin:20px auto;width:90%;text-align:center"><div>感谢支持！</div><button id="rewardButton" disable="enable" onclick="var qr = document.getElementById("QR"); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}"><span>打赏</span></button><div id="QR" style="display:none"><div id="wechat" style="display:inline-block"><img id="wechat_qr" src="/images/wechatpay.gif" alt="李瑞豪 微信支付"><p>微信支付</p></div><div id="alipay" style="display:inline-block"><img id="alipay_qr" src="/images/alipay.gif" alt="李瑞豪 支付宝"><p>支付宝</p></div></div></div></div><div><ul class="post-copyright"><li class="post-copyright-author"><strong>本文作者： </strong>李瑞豪</li><li class="post-copyright-link"><strong>本文链接：</strong> <a href="https://lruihao.cn/TaoTao要吃鸡.html" title="TaoTao要吃鸡">https://lruihao.cn/TaoTao要吃鸡.html</a></li><li class="post-copyright-license"><strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow noopener noreferrer" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！</li></ul></div><footer class="post-footer"><div class="post-tags"><a href="/tags/背包问题/" rel="tag"><i class="fa fa-tag"></i> 背包问题</a> <a href="/tags/Nowcoder/" rel="tag"><i class="fa fa-tag"></i> Nowcoder</a></div><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/Wannafly挑战赛18-序列.html" rel="next" title="Wannafly挑战赛18-序列"><i class="fa fa-chevron-left"></i> Wannafly挑战赛18-序列</a></div><span class="post-nav-divider"></span><div class="post-nav-prev post-nav-item"><a href="/深搜广搜.html" rel="prev" title="深搜广搜">深搜广搜 <i class="fa fa-chevron-right"></i></a></div></div></footer></div></article><div class="post-spread"></div></div></div><div class="comments" id="comments"></div></div><div class="sidebar-toggle"><div class="sidebar-toggle-line-wrap"><span class="sidebar-toggle-line sidebar-toggle-line-first"></span> <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span> <span class="sidebar-toggle-line sidebar-toggle-line-last"></span></div></div><aside id="sidebar" class="sidebar"><div id="sidebar-dimmer"></div><div class="sidebar-inner"><section class="site-overview-wrap sidebar-panel sidebar-panel-active"><div class="site-overview"><div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person"><img class="site-author-image" itemprop="image" src="/images/avatar.png" alt="李瑞豪"><p class="site-author-name" itemprop="name">李瑞豪</p><p class="site-description motion-element" itemprop="description">so far so good</p></div><nav class="site-state motion-element"><div class="site-state-item site-state-posts"><a href="/archives/"><span class="site-state-item-count">96</span> <span class="site-state-item-name">日志</span></a></div><div class="site-state-item site-state-categories"><a href="/categories/index.html"><span class="site-state-item-count">20</span> <span class="site-state-item-name">分类</span></a></div><div class="site-state-item site-state-tags"><a href="/tags/index.html"><span class="site-state-item-count">56</span> <span class="site-state-item-name">标签</span></a></div></nav><div class="feed-link motion-element"><a href="/atom.xml" rel="alternate"><i class="fa fa-rss"></i> RSS</a></div><div class="links-of-author motion-element"><span class="links-of-author-item"><a href="https://github.com/Lruihao" target="_blank" title="GitHub" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-github"></i>GitHub</a> </span><span class="links-of-author-item"><a href="https://blog.csdn.net/qq_39520417" target="_blank" title="CSDN" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-contao"></i>CSDN</a> </span><span class="links-of-author-item"><a href="https://weibo.com/liahao" target="_blank" title="微博" rel="external nofollow noopener noreferrer"><i class="fa fa-fw fa-weibo"></i>微博</a> </span><span class="links-of-author-item"><a href="/images/wechat.png" target="_blank" title="微信" rel="external nofollow"><i class="fa fa-fw fa-wechat"></i>微信</a> </span><span class="links-of-author-item"><a href="/images/qq.jpg" target="_blank" title="QQ" rel="external nofollow"><i class="fa fa-fw fa-qq"></i>QQ</a> </span><span class="links-of-author-item"><a href="mailto:[email protected]" target="_blank" title="E-Mail" rel="external nofollow"><i class="fa fa-fw fa-envelope"></i>E-Mail</a></span></div><div class="links-of-blogroll motion-element links-of-blogroll-inline"><div class="links-of-blogroll-title"><i class="fa fa-fw fa-globe"></i> 书签</div><ul class="links-of-blogroll-list"><li class="links-of-blogroll-item"><a href="/friends.html" title="友情链接" target="_blank">友情链接</a></li><li class="links-of-blogroll-item"><a href="/donators.html" title="赞助记录" target="_blank">赞助记录</a></li><li class="links-of-blogroll-item"><a href="/bugs.html" title="维护日志" target="_blank">维护日志</a></li><li class="links-of-blogroll-item"><a href="/links.html" title="收藏夹" target="_blank">收藏夹</a></li></ul></div></div></section></div></aside></div></main><footer id="footer" class="footer"><div class="footer-inner"><div class="copyright"><font color="black" face="STLiti">All Copyright Reserved </font><font color="black">©</font> <font color="black" face="STLiti"><span itemprop="copyrightYear">2018</span></font> <span class="with-love" id="animate"><i class="fa fa-heartbeat"></i> </span><span class="author" itemprop="copyrightHolder" style="font-family:MMT;font-size:120%;font-weight:700;color:#444">李瑞豪</span></div><div class="busuanzi-count"><script src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><font color="DarkSlateGray" face="STLiti"><span class="site-uv" title="总访客量"><i class="fa fa-user"></i> <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>人次<span class="post-meta-divider">|</span><i class="fa fa-edit" title="总字数"></i> <span class="post-count">48.2k</span>字, <span id="timeDate" title="网站运行时间">载入天数...</span><span id="times" title="网站运行时间">载入时分秒...</span><span class="post-meta-divider">|</span> </span></font><font color="DarkSlateGray" face="STLiti"><span class="site-pv" title="总访问量"><i class="fa fa-eye"></i> <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>次</span></font></div><div style="font-family:STLiti;display:inline-block;height:20px;line-height:20px"><a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=43030402000254" rel="external nofollow noopener noreferrer"><img src="/images/gov.png" style="float:left">湘公网安备 43030402000254号</a> <span class="post-meta-divider" style="color:#555">|</span><span><a href="http://www.miitbeian.gov.cn" target="_blank" rel="external nofollow noopener noreferrer">湘ICP备18020535号</a></span></div></div></footer><div class="back-to-top"><i class="fa fa-arrow-up"></i> <span id="scrollpercent"><span>0</span>%</span></div></div><script>var now=new Date;function createtime(){var n=new Date("05/28/2018 20:01:01");now.setTime(now.getTime()+250),days=(now-n)/1e3/60/60/24,dnum=Math.floor(days),hours=(now-n)/1e3/60/60-24*dnum,hnum=Math.floor(hours),1==String(hnum).length&&(hnum="0"+hnum),minutes=(now-n)/1e3/60-1440*dnum-60*hnum,mnum=Math.floor(minutes),1==String(mnum).length&&(mnum="0"+mnum),seconds=(now-n)/1e3-86400*dnum-3600*hnum-60*mnum,snum=Math.round(seconds),1==String(snum).length&&(snum="0"+snum),document.getElementById("timeDate").innerHTML=dnum+" 天",document.getElementById("times").innerHTML=hnum+" 时"+mnum+" 分"+snum+" 秒"}setInterval("createtime()",250)</script><script type="text/javascript" src="/js/src/night.js"></script><div class="cover"></div><script type="text/javascript" src="/js/src/crash_cheat.js"></script><script src="/js/src/activate-power-mode.js"></script><script>POWERMODE.colorful=!0,POWERMODE.shake=!1,document.body.addEventListener("input",POWERMODE)</script><canvas class="fireworks" style="position:fixed;left:0;top:0;z-index:1;pointer-events:none"></canvas><script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script><script type="text/javascript" src="/js/src/fireworks.js"></script><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script><script type="text/javascript" src="/js/src/utils.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/motion.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/affix.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/schemes/pisces.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/post-details.js?v=6.3.0"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=6.3.0"></script><script src="//cdn1.lncld.net/static/js/3.0.4/av-min.js"></script><script src="//unpkg.com/valine@latest/dist/Valine.min.js"></script><script type="text/javascript">var GUEST=["nick","mail","link"],guest="nick,mail,link";guest=guest.split(",").filter(function(e){return-1<GUEST.indexOf(e)}),new Valine({av:AV,el:"#comments",verify:!1,notify:!1,appId:"7HwTRT0Q0Tfrat6ugrT6P67c-gzGzoHsz",appKey:"mhTY1kuUmviCtQwkwOASfsfD",placeholder:"ヾﾉ≧∀≦)o来啊，快活啊!填写邮箱能很快收到我的回复喔！",avatar:"monsterid",guest_info:guest,pageSize:"15"})</script><script type="text/javascript">// Popup Window;
var isfetched = false;
var isXml = true;
// Search DB path;
var search_path = "search.xml";
if (search_path.length === 0) {
search_path = "search.xml";
} else if (/json$/i.test(search_path)) {
isXml = false;
}
var path = "/" + search_path;
// monitor main search box;
var onPopupClose = function (e) {
$('.popup').hide();
$('#local-search-input').val('');
$('.search-result-list').remove();
$('#no-result').remove();
$(".local-search-pop-overlay").remove();
$('body').css('overflow', '');
}
function proceedsearch() {
$("body")
.append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
.css('overflow', 'hidden');
$('.search-popup-overlay').click(onPopupClose);
$('.popup').toggle();
var $localSearchInput = $('#local-search-input');
$localSearchInput.attr("autocapitalize", "none");
$localSearchInput.attr("autocorrect", "off");
$localSearchInput.focus();
}
// search function;
var searchFunc = function(path, search_id, content_id) {
'use strict';
// start loading animation
$("body")
.append('<div class="search-popup-overlay local-search-pop-overlay">' +
'<div id="search-loading-icon">' +
'<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
'</div>' +
'</div>')
.css('overflow', 'hidden');
$("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');
$.ajax({
url: path,
dataType: isXml ? "xml" : "json",
async: true,
success: function(res) {
// get the contents from search data
isfetched = true;
$('.popup').detach().appendTo('.header-inner');
var datas = isXml ? $("entry", res).map(function() {
return {
title: $("title", this).text(),
content: $("content",this).text(),
url: $("url" , this).text()
};
}).get() : res;
var input = document.getElementById(search_id);
var resultContent = document.getElementById(content_id);
var inputEventFunction = function() {
var searchText = input.value.trim().toLowerCase();
var keywords = searchText.split(/[\s\-]+/);
if (keywords.length > 1) {
keywords.push(searchText);
}
var resultItems = [];
if (searchText.length > 0) {
// perform local searching
datas.forEach(function(data) {
var isMatch = false;
var hitCount = 0;
var searchTextCount = 0;
var title = data.title.trim();
var titleInLowerCase = title.toLowerCase();
var content = data.content.trim().replace(/<[^>]+>/g,"");
var contentInLowerCase = content.toLowerCase();
var articleUrl = decodeURIComponent(data.url);
var indexOfTitle = [];
var indexOfContent = [];
// only match articles with not empty titles
if(title != '') {
keywords.forEach(function(keyword) {
function getIndexByWord(word, text, caseSensitive) {
var wordLen = word.length;
if (wordLen === 0) {
return [];
}
var startPosition = 0, position = [], index = [];
if (!caseSensitive) {
text = text.toLowerCase();
word = word.toLowerCase();
}
while ((position = text.indexOf(word, startPosition)) > -1) {
index.push({position: position, word: word});
startPosition = position + wordLen;
}
return index;
}
indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
});
if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
isMatch = true;
hitCount = indexOfTitle.length + indexOfContent.length;
}
}
// show search results
if (isMatch) {
// sort index by position of keyword
[indexOfTitle, indexOfContent].forEach(function (index) {
index.sort(function (itemLeft, itemRight) {
if (itemRight.position !== itemLeft.position) {
return itemRight.position - itemLeft.position;
} else {
return itemLeft.word.length - itemRight.word.length;
}
});
});
// merge hits into slices
function mergeIntoSlice(text, start, end, index) {
var item = index[index.length - 1];
var position = item.position;
var word = item.word;
var hits = [];
var searchTextCountInSlice = 0;
while (position + word.length <= end && index.length != 0) {
if (word === searchText) {
searchTextCountInSlice++;
}
hits.push({position: position, length: word.length});
var wordEnd = position + word.length;
// move to next position of hit
index.pop();
while (index.length != 0) {
item = index[index.length - 1];
position = item.position;
word = item.word;
if (wordEnd > position) {
index.pop();
} else {
break;
}
}
}
searchTextCount += searchTextCountInSlice;
return {
hits: hits,
start: start,
end: end,
searchTextCount: searchTextCountInSlice
};
}
var slicesOfTitle = [];
if (indexOfTitle.length != 0) {
slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
}
var slicesOfContent = [];
while (indexOfContent.length != 0) {
var item = indexOfContent[indexOfContent.length - 1];
var position = item.position;
var word = item.word;
// cut out 100 characters
var start = position - 20;
var end = position + 80;
if(start < 0){
start = 0;
}
if (end < position + word.length) {
end = position + word.length;
}
if(end > content.length){
end = content.length;
}
slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
}
// sort slices in content by search text's count and hits' count
slicesOfContent.sort(function (sliceLeft, sliceRight) {
if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
return sliceRight.searchTextCount - sliceLeft.searchTextCount;
} else if (sliceLeft.hits.length !== sliceRight.hits.length) {
return sliceRight.hits.length - sliceLeft.hits.length;
} else {
return sliceLeft.start - sliceRight.start;
}
});
// select top N slices in content
var upperBound = parseInt('1');
if (upperBound >= 0) {
slicesOfContent = slicesOfContent.slice(0, upperBound);
}
// highlight title and content
function highlightKeyword(text, slice) {
var result = '';
var prevEnd = slice.start;
slice.hits.forEach(function (hit) {
result += text.substring(prevEnd, hit.position);
var end = hit.position + hit.length;
result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
prevEnd = end;
});
result += text.substring(prevEnd, slice.end);
return result;
}
var resultItem = '';
if (slicesOfTitle.length != 0) {
resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
} else {
resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
}
slicesOfContent.forEach(function (slice) {
resultItem += "<a href='" + articleUrl + "'>" +
"<p class=\"search-result\">" + highlightKeyword(content, slice) +
"...</p>" + "</a>";
});
resultItem += "</li>";
resultItems.push({
item: resultItem,
searchTextCount: searchTextCount,
hitCount: hitCount,
id: resultItems.length
});
}
})
};
if (keywords.length === 1 && keywords[0] === "") {
resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
} else if (resultItems.length === 0) {
resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
} else {
resultItems.sort(function (resultLeft, resultRight) {
if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
return resultRight.searchTextCount - resultLeft.searchTextCount;
} else if (resultLeft.hitCount !== resultRight.hitCount) {
return resultRight.hitCount - resultLeft.hitCount;
} else {
return resultRight.id - resultLeft.id;
}
});
var searchResultList = '<ul class=\"search-result-list\">';
resultItems.forEach(function (result) {
searchResultList += result.item;
})
searchResultList += "</ul>";
resultContent.innerHTML = searchResultList;
}
}
if ('auto' === 'auto') {
input.addEventListener('input', inputEventFunction);
} else {
$('.search-icon').click(inputEventFunction);
input.addEventListener('keypress', function (event) {
if (event.keyCode === 13) {
inputEventFunction();
}
});
}
// remove loading animation
$(".local-search-pop-overlay").remove();
$('body').css('overflow', '');
proceedsearch();
}
});
}
// handle and trigger popup window;
$('.popup-trigger').click(function(e) {
e.stopPropagation();
if (isfetched === false) {
searchFunc(path, 'local-search-input', 'local-search-result');
} else {
proceedsearch();
};
});
$('.popup-btn-close').click(onPopupClose);
$('.popup').click(function(e){
e.stopPropagation();
});
$(document).on('keyup', function (event) {
var shouldDismissSearchPopup = event.which === 27 &&
$('.search-popup').is(':visible');
if (shouldDismissSearchPopup) {
onPopupClose();
}
});</script><script>!function(){var t=document.createElement("script"),e=window.location.protocol.split(":")[0];t.src="https"===e?"https://zz.bdstatic.com/linksubmit/push.js":"http://push.zhanzhang.baidu.com/push.js";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(t,s)}()</script><script src="/lib/pangu/dist/pangu.min.js?v=3.3"></script><script type="text/javascript">pangu.spacingPage()</script><style>.copy-btn{display:inline-block;padding:6px 12px;font-size:13px;font-weight:700;line-height:20px;color:#333;white-space:nowrap;vertical-align:middle;cursor:pointer;background-color:#eee;background-image:linear-gradient(#fcfcfc,#eee);border:1px solid #d5d5d5;border-radius:3px;user-select:none;outline:0}.highlight-wrap .copy-btn{transition:opacity .3s ease-in-out;opacity:0;padding:2px 6px;position:absolute;right:4px;top:8px}.highlight-wrap .copy-btn:focus,.highlight-wrap:hover .copy-btn{opacity:1}.highlight-wrap{position:relative}</style><script>$(".highlight").each(function(t,e){var n=$("<div>").addClass("highlight-wrap");$(e).after(n),n.append($("<button>").addClass("copy-btn").append("复制").on("click",function(t){var e=$(this).parent().find(".code").find(".line").map(function(t,e){return $(e).text()}).toArray().join("\n"),n=document.createElement("textarea");document.body.appendChild(n),n.style.position="absolute",n.style.top="0px",n.style.left="0px",n.value=e,n.select(),n.focus();var o=document.execCommand("copy");document.body.removeChild(n),o?$(this).text("复制成功"):$(this).text("复制失败"),$(this).blur()})).on("mouseleave",function(t){var e=$(this).find(".copy-btn");setTimeout(function(){e.text("复制")},300)}).append(e)})</script></body></html>