标签:动态规划

【考试总结】考试体验极差的一次考试 ——litble

20171030 考试总结

考试策略

T1和异或有关......异或的东西我都不是很懂,估计做不出来,打个20分暴力。

T2是数学题......数学我完全学不懂啊,估计做不出来,打个暴力....[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【考试总结】一只蒟蒻再次暴露了自己的本性 ——litble

考试策略

​ QAQ今天没考好真的是考试策略的锅。首先看到第一题“卷积”就懵了,题目都看不懂,然后什么zyf啊boshi啊xzy啊全部会做T1,感觉自己要爆炸了。于是做T2,做了一个多小时写了[......]

[继续阅读= ̄ω ̄=]

Read MoreView 3 Comments

【考试总结】NOIp Day3 模拟试 ——litble

考试策略

T1不可做,T2不可做,T3不可做......

今天考试看到题目第一句话就是:“凸包是什么”,第二句话是:“Day3是什么”,后来经WY大佬指示才发现是“NOIp”模拟,注意,只有“p”[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 组合数问题 动态规划 NOIP 2016 LUOGU – 2822

1. 题目

传送门= ̄ω ̄=

2. 题解

感觉自己noip2016在仙游。。。
为什么这么水的题目没想出来?当时也学了组合数递推求$C_n^k$
先预处理出$C_n^k\ mod\[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 子串 动态规划 NOIP2015 LUOGU – 2679

1. 题目

传送门= ̄ω ̄=

2. 题解

首先不难想到:
设$f[i][j][k]$为第一个字符串的前i个字符和第二个字符串的前j个字符匹配,用了k个子串时的方案数。
那么$f[i][j][k][......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】从harbingers谈对斜率优化和凸包的全新认识 -boshi

在今天的考试中,我们遇到了一道极其恶心的题。看似是斜率优化的树形Dp,实际暗藏玄机。

harbingers

题意:给定一棵树,除1号以外的每个节点上都有一个快递小哥。每个节点都可能有快递要送到一号[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Bank notes 多重背包单调队列优化 BZOJ – 1531

1. 题目

传送门= ̄ω ̄=

注:这是个权限题。。。不过用博客上的bzoj离线版可以看到题目

2. 题解

单调队列优化多重背包模板题。。。
(我这么弱只做的动模板题了)

朴素的递推式是:$f[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】多重背包单调队列合集 -boshi

T1.Coins(POJ1742)

多重背包最基本的状态转移方程是这样的: 用f[i][j]表示前i个物品装进背包占容量为j时的最大价值。
$$

题意:

求用n种硬币每种c[i]个最多可以凑出多[......]

[继续阅读= ̄ω ̄=]

Read MoreView 3 Comments

【题解】 Coins 多重背包优化 POJ – 1742 —— by 蒟蒻XZY

1. 题目

传送门= ̄ω ̄=

题意:给你n种硬币,第i种的面值是ai,个数时ci,求这些硬币能凑成区间$[1,m]$间的那些值

2. 题解

普通的多重背包复杂度为$O(n\times m\ti[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】多重背包 (HDU2191) -boshi

题意:

给定一些物品的价值、大小、数量。求一个大小为m的背包最多装得下多少价值的物品。

虽然这道题乱搞都可以AC,但是我们还是实用单调队列优化

这里的f[i]表示容量为i的背包可以装下的最大价值[......]

[继续阅读= ̄ω ̄=]

Read MoreComment