-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathindex.html
350 lines (319 loc) · 45.9 KB
/
index.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
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>WuDocs - 一站式学习网站</title><meta name="author" content="划船全靠浪"><meta name="copyright" content="划船全靠浪"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="逆水行舟 不进则退">
<meta property="og:type" content="website">
<meta property="og:title" content="WuDocs">
<meta property="og:url" content="https://creating001.github.io/index.html">
<meta property="og:site_name" content="WuDocs">
<meta property="og:description" content="逆水行舟 不进则退">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://creating001.github.io/img/logo/avatar.webp">
<meta property="article:author" content="划船全靠浪">
<meta property="article:tag" content="WuDocs">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://creating001.github.io/img/logo/avatar.webp"><link rel="shortcut icon" href="/img/logo/logo.svg"><link rel="canonical" href="https://creating001.github.io/index.html"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: {"appId":"8TCQJ3T245","apiKey":"f141b7227a86cdc56174ee1740c60067","indexName":"dev_hexo","hits":{"per_page":10},"languages":{"input_placeholder":"搜索文章","hits_empty":"找不到您查询的内容：${query}","hits_stats":"找到 ${hits} 条结果，用时 ${time} 毫秒"}},
localSearch: undefined,
translate: {"defaultEncoding":2,"translateDelay":100,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
noticeOutdate: undefined,
highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":500},
copy: {
success: '复制成功',
error: '复制错误',
noSupport: '浏览器不支持'
},
relativeDate: {
homepage: true,
post: true
},
runtime: '天',
dateSuffix: {
just: '刚刚',
min: '分钟前',
hour: '小时前',
day: '天前',
month: '个月前'
},
copyright: {"limitCount":50,"languages":{"author":"作者: 划船全靠浪","link":"链接: ","source":"来源: WuDocs","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
lightbox: 'fancybox',
Snackbar: undefined,
infinitegrid: {
js: 'https://cdn.jsdelivr.net/npm/@egjs/infinitegrid/dist/infinitegrid.min.js',
buttonText: '加载更多'
},
isPhotoFigcaption: false,
islazyload: false,
isAnchor: false,
percent: {
toc: true,
rightside: true,
},
autoDarkmode: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: 'WuDocs',
isPost: false,
isHome: true,
isHighlightShrink: undefined,
isToc: false,
postUpdate: '2023-12-19 15:04:38'
}</script><script>(win=>{
win.saveToLocal = {
set: (key, value, ttl) => {
if (ttl === 0) return
const now = Date.now()
const expiry = now + ttl * 86400000
const item = {
value,
expiry
}
localStorage.setItem(key, JSON.stringify(item))
},
get: key => {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = Date.now()
if (now > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
Object.keys(attr).forEach(key => {
script.setAttribute(key, attr[key])
})
document.head.appendChild(script)
})
win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
const link = document.createElement('link')
link.rel = 'stylesheet'
link.href = url
if (id) link.id = id
link.onerror = reject
link.onload = link.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
link.onload = link.onreadystatechange = null
resolve()
}
document.head.appendChild(link)
})
win.activateDarkMode = () => {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = () => {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><link rel="stylesheet" href="/fonts/font.css"><meta name="baidu-site-verification" content="codeva-FYsip8Orcx" /><meta name="google-site-verification" content="1hfP4Hpw0wjx70Y3PavnJnkd8jUxJ8F9T3dFNqH84QI" /><meta name="msvalidate.01" content="E6CCAF4880BBF703D5DFB67DA28ACDD2" /><meta name="referrer" content="no-referrer-when-downgrade" /><meta name="generator" content="Hexo 6.3.0"><link rel="alternate" href="/atom.xml" title="WuDocs" type="application/atom+xml">
</head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><script>(()=>{
const $loadingBox = document.getElementById('loading-box')
const $body = document.body
const preloader = {
endLoading: () => {
$body.style.overflow = ''
$loadingBox.classList.add('loaded')
},
initLoading: () => {
$body.style.overflow = 'hidden'
$loadingBox.classList.remove('loaded')
}
}
preloader.initLoading()
window.addEventListener('load',() => { preloader.endLoading() })
if (false) {
document.addEventListener('pjax:send', () => { preloader.initLoading() })
document.addEventListener('pjax:complete', () => { preloader.endLoading() })
}
})()</script><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/img/logo/avatar.webp" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">8</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">10</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">3</div></a></div><hr class="custom-hr"/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa-sharp fa-solid fa-compass"></i><span> 目录</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-paperclip"></i><span> 链接</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-heart"></i><span> 关于</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/about/"><i class="fa-fw fa-solid fa-laptop-code"></i><span> 自己</span></a></li></ul></div></div></div></div><div class="page" id="body-wrap"><header class="full_page" id="page-header" style="background-image: url('/img/background/01.webp')"><nav id="nav"><span id="blog-info"><a href="/" title="WuDocs"><img class="site-icon" src="/img/logo/logo.svg"/><span class="site-name">WuDocs</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa-sharp fa-solid fa-compass"></i><span> 目录</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 归档</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-heartbeat"></i><span> 清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/gallery/"><i class="fa-fw fas fa-images"></i><span> 照片</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-paperclip"></i><span> 链接</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-heart"></i><span> 关于</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/about/"><i class="fa-fw fa-solid fa-laptop-code"></i><span> 自己</span></a></li></ul></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="site-info"><h1 id="site-title">WuDocs</h1><div id="site-subtitle"><span id="subtitle"></span></div><div id="site_social_icons"><a class="social-icon" href="https://github.com/creating001" target="_blank" title="Github"><i class="fab fa-github" style="color: #000000;"></i></a><a class="social-icon" href="https://space.bilibili.com/687396310" target="_blank" title="Bilibili"><i class="fa-brands fa-bilibili" style="color: #000000;"></i></a><a class="social-icon" href="/./atom.xml" target="_blank" title="RSS"><i class="fas fa-rss" style="color: #000000;"></i></a></div></div><div id="scroll-down"><i class="fas fa-angle-down scroll-down-effects"></i></div></header><main class="layout" id="content-inner"><div class="recent-posts" id="recent-posts"><div class="recent-post-item"><div class="post_cover left"><a href="/2023/05/31/graph-0-save/" title="图论之图的存储"><img class="post-bg" src="/img/background/51.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="图论之图的存储"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/31/graph-0-save/" title="图论之图的存储">图论之图的存储</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-31T08:26:32.000Z" title="发表于 2023-05-31 16:26:32">2023-05-31</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:47:41.490Z" title="更新于 2023-06-02 19:47:41">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E5%9B%BE%E8%AE%BA/">图论</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%9B%BE%E8%AE%BA/">图论</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E5%9B%BE%E7%9A%84%E5%AD%98%E5%82%A8/">图的存储</a></span></div><div class="content">直接存边
方法
使用一个数组来存边，数组中的每个元素都包含一条边的起点与终点（带边权的图还包含边权）。（或者使用多个数组分别存起点，终点和边权。）
代码实现
1234567891011121314151617181920212223242526272829struct Edge { int u, v;};const int N = 1e5;int n, m;Edge arr[N];bool vis[N];bool find_edge(int u, int v) { for (int i = 1; i <= m; i++) { if (arr[i].u == u && arr[i].v == v) return true; } return false;}void dfs(int u) { if (vis[u]) return; vis[u] = true; for (int i = 1; i <= m; i++) { ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2023/05/28/dp-6-digit/" title="动态规划之数位dp"><img class="post-bg" src="/img/background/22.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之数位dp"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/28/dp-6-digit/" title="动态规划之数位dp">动态规划之数位dp</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-28T12:20:58.000Z" title="发表于 2023-05-28 20:20:58">2023-05-28</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:43:09.538Z" title="更新于 2023-06-02 19:43:09">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E6%95%B0%E4%BD%8Ddp/">数位dp</a></span></div><div class="content">引入
数位是指把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。
数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：
要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大（比如 10^18），暴力枚举验证会超时。
数位 DP 的基本原理
考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的 ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2023/05/25/dp-5-state/" title="动态规划之状压dp"><img class="post-bg" src="/img/background/19.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之状压dp"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/25/dp-5-state/" title="动态规划之状压dp">动态规划之状压dp</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-25T12:20:58.000Z" title="发表于 2023-05-25 20:20:58">2023-05-25</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:42:24.640Z" title="更新于 2023-06-02 19:42:24">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E7%8A%B6%E5%8E%8Bdp/">状压dp</a></span></div><div class="content">定义
状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。
引入
题目描述
互不侵犯
在 N*N 的棋盘里面放 K 个国王（1 <= N <= 9, 1 <= K <= N * N），使他们互不攻击，共有多少种摆放方案。
国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。
思路分析
设 dp(i,j,l) 表示前 i 行，第 i 行的状态为 j，且棋盘上已经放置 l 个国王时的合法方案数。
对于编号为 j 的状态，我们用二进制整数 state(j) 表示国王的放置情况，state(j) 的某个二进制位为 0 表示对应位置不放国王，为 1 表示在对应位置上放置国王；用 stateCount(j) 表示该状态的国王个数，即二进制数 state(j) 中 1 的个数。例如，如下图所示的状态可用二进制数 100101 来表示（棋盘左边对应二进制低位），则有 state(j)=100101, stateCount(j)=3。
设当前行的状态为 j，上一行的状态为 k，在保证当前行和上一行不冲突的前提下，枚举所有可 ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2023/05/22/dp-4-tree/" title="动态规划之树形dp"><img class="post-bg" src="/img/background/16.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之树形dp"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/22/dp-4-tree/" title="动态规划之树形dp">动态规划之树形dp</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-21T17:35:30.000Z" title="发表于 2023-05-22 01:35:30">2023-05-22</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:42:05.096Z" title="更新于 2023-06-02 19:42:05">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E6%A0%91%E5%BD%A2dp/">树形dp</a></span></div><div class="content">概括
树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。
基础
没有上司的舞会
某大学有 n 个职员，编号为 1 --- N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 Ai，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
思路分析
我们设 f(i,0/1) 代表以 i 为根的子树的最优解(第二维的值为 0 代表 i 不参加舞会的情况，1 代表 i 参加舞会的情况)。
对于每个状态，都存在两种决策(其中下面的 x 都是 i 的儿子)：
上司不参加舞会时，下属可以参加，也可以不参加，此时有 f(i,0) = sum{max{f(x,1),f(x,0)}}。
上司参加舞会时，下属都不会参加，此时有 f(i,1) = sum{f(x,0)} + Ai。
我们可以通过 DFS， ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2023/05/19/dp-3-interval/" title="动态规划之区间dp"><img class="post-bg" src="/img/background/06.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之区间dp"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/19/dp-3-interval/" title="动态规划之区间dp">动态规划之区间dp</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-18T17:22:27.000Z" title="发表于 2023-05-19 01:22:27">2023-05-19</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:42:02.749Z" title="更新于 2023-06-02 19:42:02">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E5%8C%BA%E9%97%B4dp/">区间dp</a></span></div><div class="content">定义
区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
令状态 f(i,j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么
f(i,j)=max{f(i,k)+f(k+1,j)+cost}f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}
f(i,j)=max{f(i,k)+f(k+1,j)+cost}
cost 为将这两组元素合并起来的代价。
性质
区间 DP 有以下特点：
合并：即将两个或多个部分进行整合，当然也可以反过来；
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
典型例题
石子合并1
在一个操场上摆放着一排 N 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的 2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将 N 堆石子合并成一堆的最小得分。
1234567891011121314151617 ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2023/05/16/dp-2-linear/" title="动态规划之线性dp"><img class="post-bg" src="/img/background/43.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之线性dp"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/16/dp-2-linear/" title="动态规划之线性dp">动态规划之线性dp</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-15T16:03:20.000Z" title="发表于 2023-05-16 00:03:20">2023-05-16</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:41:58.879Z" title="更新于 2023-06-02 19:41:58">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E7%BA%BF%E6%80%A7dp/">线性dp</a></span></div><div class="content">概述
线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。
线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。
因此，除了少量问题（如LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。
典型题目
LIS
线性dp
12345678910class Solution {public: int lengthOfLIS(vector<int>& nums) { vector<int> dp(nums.size(), 1); for (int i = 1; i < dp.size(); i++) for (int j = 0; j < i; j++) if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1); return ...</div></div></div><div class="recent-post-item"><div class="post_cover left"><a href="/2023/05/13/dp-1-knapsack/" title="动态规划之背包问题"><img class="post-bg" src="/img/background/01.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之背包问题"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/13/dp-1-knapsack/" title="动态规划之背包问题">动态规划之背包问题</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-13T01:30:10.000Z" title="发表于 2023-05-13 09:30:10">2023-05-13</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:42:32.356Z" title="更新于 2023-06-02 19:42:32">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/">背包问题</a></span></div><div class="content">01背包
01背包问题
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi ，价值是 wi 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
1234567891011121314int n;int v;cin >> n >> v;vector<int> arrV(n);vector<int> arrW(n);for (int i = 0; i < n; i++) { cin >> arrV[i]; cin >> arrW[i];}vector<int> dp(v + 1, 0);for (int i = 1; i <= n; i++) for (int j = v; j >= arrV[i - 1]; j--) dp[j] = max(dp[j], arrW[i - 1] + dp[j - arrV[i - 1]]);cout << dp.back( ...</div></div></div><div class="recent-post-item"><div class="post_cover right"><a href="/2023/05/10/dp-0-memo/" title="动态规划之记忆化搜索"><img class="post-bg" src="/img/background/21.webp" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="动态规划之记忆化搜索"></a></div><div class="recent-post-info"><a class="article-title" href="/2023/05/10/dp-0-memo/" title="动态规划之记忆化搜索">动态规划之记忆化搜索</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">发表于</span><time class="post-meta-date-created" datetime="2023-05-10T15:34:40.000Z" title="发表于 2023-05-10 23:34:40">2023-05-10</time><span class="article-meta-separator">|</span><i class="fas fa-history"></i><span class="article-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-06-02T11:32:16.295Z" title="更新于 2023-06-02 19:32:16">2023-06-02</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right article-meta-link"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a></span><span class="article-meta tags"><span class="article-meta-separator">|</span><i class="fas fa-tag"></i><a class="article-meta__tags" href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">动态规划</a><span class="article-meta-link">•</span><a class="article-meta__tags" href="/tags/%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/">记忆化搜索</a></span></div><div class="content">定义
记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
因为记忆化搜索确保了每个状态只访问一次，它也是一种常见的动态规划实现方式。
引入
采药
题目描述
山洞里有 M 株不同的草药，采每一株都需要一些时间 t_i，每一株也有它自身的价值 v_i。给你一段时间 T，在这段时间里，你可以采到一些草药。让采到的草药的总价值最大。
暴力DFS做法
很容易实现这样一个朴素的搜索做法：在搜索时记录下当前准备选第几个物品、剩余的时间是多少、已经获得的价值是多少这三个参数，然后枚举当前物品是否被选，转移到相应的状态。
123456789101112131415161718192021222324252627282930struct node { int time; int value; node() = default; node(int time, int value) : time(time), value(value) {}};node arr[105];int T, M;int ans = ...</div></div></div><nav id="pagination"><div class="pagination"><span class="page-number current">1</span></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="/img/logo/avatar.webp" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">划船全靠浪</div><div class="author-info__description">逆水行舟 不进则退</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">8</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">10</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">3</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/creating001"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/creating001" target="_blank" title="Github"><i class="fab fa-github" style="color: #000000;"></i></a><a class="social-icon" href="https://space.bilibili.com/687396310" target="_blank" title="Bilibili"><i class="fa-brands fa-bilibili" style="color: #000000;"></i></a><a class="social-icon" href="/./atom.xml" target="_blank" title="RSS"><i class="fas fa-rss" style="color: #000000;"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content">一站式学习网站</div></div><div class="sticky_layout"><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/05/31/graph-0-save/" title="图论之图的存储">图论之图的存储</a><time datetime="2023-05-31T08:26:32.000Z" title="发表于 2023-05-31 16:26:32">2023-05-31</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/05/28/dp-6-digit/" title="动态规划之数位dp">动态规划之数位dp</a><time datetime="2023-05-28T12:20:58.000Z" title="发表于 2023-05-28 20:20:58">2023-05-28</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/05/25/dp-5-state/" title="动态规划之状压dp">动态规划之状压dp</a><time datetime="2023-05-25T12:20:58.000Z" title="发表于 2023-05-25 20:20:58">2023-05-25</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/05/22/dp-4-tree/" title="动态规划之树形dp">动态规划之树形dp</a><time datetime="2023-05-21T17:35:30.000Z" title="发表于 2023-05-22 01:35:30">2023-05-22</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/05/19/dp-3-interval/" title="动态规划之区间dp">动态规划之区间dp</a><time datetime="2023-05-18T17:22:27.000Z" title="发表于 2023-05-19 01:22:27">2023-05-19</time></div></div></div></div><div class="card-widget card-categories"><div class="item-headline">
<i class="fas fa-folder-open"></i>
<span>分类</span>
</div>
<ul class="card-category-list" id="aside-cat-list">
<li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E5%9B%BE%E8%AE%BA/"><span class="card-category-list-name">图论</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E7%AE%97%E6%B3%95/"><span class="card-category-list-name">算法</span><span class="card-category-list-count">7</span></a><ul class="card-category-list child"><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E7%AE%97%E6%B3%95/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/"><span class="card-category-list-name">动态规划</span><span class="card-category-list-count">7</span></a></li></ul></li>
</ul></div><div class="card-widget card-tags"><div class="item-headline"><i class="fas fa-tags"></i><span>标签</span></div><div class="card-tag-cloud"><a href="/tags/%E7%8A%B6%E5%8E%8Bdp/" style="font-size: 1.1em; color: #999">状压dp</a> <a href="/tags/%E5%8C%BA%E9%97%B4dp/" style="font-size: 1.1em; color: #999">区间dp</a> <a href="/tags/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" style="font-size: 1.5em; color: #99a9bf">动态规划</a> <a href="/tags/%E6%A0%91%E5%BD%A2dp/" style="font-size: 1.1em; color: #999">树形dp</a> <a href="/tags/%E5%9B%BE%E7%9A%84%E5%AD%98%E5%82%A8/" style="font-size: 1.1em; color: #999">图的存储</a> <a href="/tags/%E5%9B%BE%E8%AE%BA/" style="font-size: 1.1em; color: #999">图论</a> <a href="/tags/%E7%BA%BF%E6%80%A7dp/" style="font-size: 1.1em; color: #999">线性dp</a> <a href="/tags/%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2/" style="font-size: 1.1em; color: #999">记忆化搜索</a> <a href="/tags/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/" style="font-size: 1.1em; color: #999">背包问题</a> <a href="/tags/%E6%95%B0%E4%BD%8Ddp/" style="font-size: 1.1em; color: #999">数位dp</a></div></div><div class="card-widget card-archives"><div class="item-headline"><i class="fas fa-archive"></i><span>归档</span></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2023/05/"><span class="card-archive-list-date">五月 2023</span><span class="card-archive-list-count">8</span></a></li></ul></div><div class="card-widget card-webinfo"><div class="item-headline"><i class="fas fa-chart-line"></i><span>网站资讯</span></div><div class="webinfo"><div class="webinfo-item"><div class="item-name">文章数目 :</div><div class="item-count">8</div></div><div class="webinfo-item"><div class="item-name">已运行时间 :</div><div class="item-count" id="runtimeshow" data-publishDate="2023-05-08T12:00:00.000Z"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">本站总字数 :</div><div class="item-count">19.8k</div></div><div class="webinfo-item"><div class="item-name">本站访客数 :</div><div class="item-count" id="busuanzi_value_site_uv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">本站总访问量 :</div><div class="item-count" id="busuanzi_value_site_pv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">最后更新时间 :</div><div class="item-count" id="last-push-date" data-lastPushDate="2023-12-19T07:04:38.523Z"><i class="fa-solid fa-spinner fa-spin"></i></div></div></div></div></div></div></main><footer id="footer" style="background-image: url('/img/background/01.webp')"><div id="footer-wrap"><div class="copyright">©2023 By 划船全靠浪</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox/fancybox.umd.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script>function panguFn () {
if (typeof pangu === 'object') pangu.autoSpacingPage()
else {
getScript('https://cdn.jsdelivr.net/npm/pangu/dist/browser/pangu.min.js')
.then(() => {
pangu.autoSpacingPage()
})
}
}
function panguInit () {
if (true){
GLOBAL_CONFIG_SITE.isPost && panguFn()
} else {
panguFn()
}
}
document.addEventListener('DOMContentLoaded', panguInit)</script><div class="js-pjax"><script>window.typedJSFn = {
init: (str) => {
window.typed = new Typed('#subtitle', Object.assign({
strings: str,
startDelay: 300,
typeSpeed: 150,
loop: true,
backSpeed: 50,
}, null))
},
run: (subtitleType) => {
if (true) {
if (typeof Typed === 'function') {
subtitleType()
} else {
getScript('https://cdn.jsdelivr.net/npm/typed.js/dist/typed.umd.min.js').then(subtitleType)
}
} else {
subtitleType()
}
}
}
</script><script>function subtitleType () {
getScript('https://sdk.jinrishici.com/v2/browser/jinrishici.js').then(() => {
jinrishici.load(result =>{
if (true) {
const sub = []
const content = result.data.content
sub.unshift(content)
typedJSFn.init(sub)
} else {
document.getElementById('subtitle').textContent = result.data.content
}
})
})
}
typedJSFn.run(subtitleType)
</script><script>(() => {
const $mermaid = document.querySelectorAll('#article-container .mermaid-wrap')
if ($mermaid.length === 0) return
const runMermaid = () => {
window.loadMermaid = true
const theme = document.documentElement.getAttribute('data-theme') === 'dark' ? 'dark' : 'default'
Array.from($mermaid).forEach((item, index) => {
const mermaidSrc = item.firstElementChild
const mermaidThemeConfig = '%%{init:{ \'theme\':\'' + theme + '\'}}%%\n'
const mermaidID = 'mermaid-' + index
const mermaidDefinition = mermaidThemeConfig + mermaidSrc.textContent
const renderFn = mermaid.render(mermaidID, mermaidDefinition)
const renderV10 = () => {
renderFn.then(({svg}) => {
mermaidSrc.insertAdjacentHTML('afterend', svg)
})
}
const renderV9 = svg => {
mermaidSrc.insertAdjacentHTML('afterend', svg)
}
typeof renderFn === 'string' ? renderV9(renderFn) : renderV10()
})
}
const loadMermaid = () => {
window.loadMermaid ? runMermaid() : getScript('https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js').then(runMermaid)
}
btf.addGlobalFn('themeChange', runMermaid, 'mermaid')
window.pjax ? loadMermaid() : document.addEventListener('DOMContentLoaded', loadMermaid)
})()</script></div><canvas class="fireworks" mobile="true"></canvas><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/fireworks.min.js"></script><script defer="defer" id="fluttering_ribbon" mobile="true" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/dist/canvas-fluttering-ribbon.min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div id="algolia-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="search-wrap"><div id="algolia-search-input"></div><hr/><div id="algolia-search-results"><div id="algolia-hits"></div><div id="algolia-pagination"></div><div id="algolia-info"><div class="algolia-stats"></div><div class="algolia-poweredBy"></div></div></div></div></div><div id="search-mask"></div><script src="https://cdn.jsdelivr.net/npm/algoliasearch/dist/algoliasearch-lite.umd.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instantsearch.js/dist/instantsearch.production.min.js"></script><script src="/js/search/algolia.js"></script></div></div></body></html>