hdu6007 Mr. Panda and Crystal dij+完全背包

我们只要求出每种宝石获得的最小花费,这道题就变成了完全背包。

我们回顾下方程 dp[v] = max(dp[v],dp[v – c[i]] + p[i]) v从1开始循环。

然后怎么求出每种宝石获得的最小花费呢?

我们回顾下题意,发现模型有些类似最短路,只不过每个点的dis是组成成[……]

Read more

hdu 6249 Alice’s Stamps DP

先删除所有被完全包含的区间。

然后对区间按照右端点排序。

dp[i][j]表示考虑前i个区间中选j个的最大覆盖面积。

然后三个转移。

dp[i][j] = dp[i – 1][j]

起传递作用

如果在i处有结尾的区间,长为l

dp[i][j] = dp[i[……]

Read more

hdu 5956 The Elder hdu 斜率优化上树

第一次知道斜率优化还能上树,构造函数传参穿窜了,过了一堆样例,de了一下午,日

BZOJ 3173: [Tjoi2013]最长上升子序列 splay dp 思维题

我们发现他按照从小到大插入,如果我插入一个值,那可能会影响非常多的上升子序列。但是如果我们反着来,每次删除一个最大的,我们只影响以他为结尾的子序列,相对而言就容易处理多了。所以我们先用平衡树,求出最终序列。

然后我们考虑常规的nlogn最长上升子序列做法,我们可以边做dp,边维护出,保持一个长[……]

Read more

hdu6403 Card Game(基环树+DP)

看着题觉得很有趣,想了很久没想出来,后来又看了题解发现,这题太好了,我得写一写。然后敲了快300行,然后上网查了别人的代码,100行就写完了,真的是感受到了差距。

网上的大神们直接用普通搜索,外加边点的数量关系,就算出来了弱联通分量,判断出了是不是树或者基环树,然后我用了tarjan和一堆定制[……]

Read more

bzoj 3675: [Apio2014]序列分割 斜率优化

首先你要发现这题有个奇妙的性质,就是说当你一个切割方案确定下来,你切的先后的顺序对最终的答案没有任何影响。

做一个简单的证明,假设a b c我们考虑先切a右侧,再切b右侧答案是

a * (b + c) + b * c

先切b右侧,再切a右侧,答案是

(a + b) * c +[……]

Read more

Noi模拟 最长路径 DP 奇妙推论

【题目描述】

在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。

Byteasar居住在1号城市,他希望从1号城市出[……]

Read more

bzoj 4602: [Sdoi2016]齿轮 dfs

找个起始点钦点一个速度,然后搜索,然后矛盾输出即可对吧。好吧,很简单吧。

开始忘记在搜索前钦点速度了,QwQ

bzoj 4562: [Haoi2016]食物链 记忆化搜索

搜就行了,注意单一物种不为食物链。