UhhhQQQU

题解

dp中的一些操作(1) 学习笔记(2) 游记(2)

/ 注册

全部文章 / 题解（共6篇）

题解|恨7不成妻

这题要求的是符合一些条件的数，明显是数位dp的套路，所以我们就向数位dp方面想。先来看条件： 1.整数中不能有7。处理方式非常简单，就是当枚举到7时直接continue掉就行了 2.整数的每一位加起来的和不是7的整数。这个也很简单，在dp数组和dfs中加入...

2020-01-14

0 744

题解|[HAOI2009]逆序对数列

这一题的题面，告诉我们是要求逆序对数为k的数列。但是，恐怖的数据范围说明了一切 n<=1000 k<=1000 这么大的数据，对于求逆序对的任何方法都是会TLE的既然按照题面的说法不行，我们就在我们的知识范围...

2020-01-11

1 840

题解|大吉大利，晚上吃鸡！

因为这道题目要求的是方案数，所以我们设一个两维数组f[i][x]作为从s(i==0)/t(i==1)到点x的最短路的条数。于是条件1就被转化为了：求两个点A和B，使得f[0][A]*f[1...

2020-01-11

9 1106

题解|Eating Together

思路：dp 设两个二维数组f1与f2，它们的定义如下： f1[i][j]：前i个数，最后一个数为j，使这i个数为升序的最小改变数 f2[i][j]：前i个数，最后一个数为j，使这i个数为降序的最小改变数首先，f1与f2的边界条件为： ...

2020-01-11

0 660

题解|数字游戏2

数位dp 题意相信大家都懂（不懂就继续读吧学好文化课吧），接下来看数据范围 1<=a,b<=231 显然，枚举是会T掉的，所以我们考虑数位dp（注意：我是用前缀和来处理出答案的，也就是最终答案为ansb-ansa-1）。 ...

2020-01-11

0 526

题解|皇宫看守

应该都不难看出这是个树形dp吧，那接下来就讲过程了。状态设置我们设置一个dp数组f[i][j]，表示以i为根的树，当前状态为j时设置看守的最小花费。 a.i表示当前结点的编号。 ...

2020-01-11

0 583