DP专场

Week1:HRBUST 1186、HDU 5519、UVA 10304、POJ 1160、HDU 5951、 HDU 5807、POJ 2018、UVA 1106、HDU 5730、HDU 6078、BZOJ 4601、LOJ 2268.

HRBUST 1186

题意

一只青蛙,在 $[0,L]$ 上从 $0$ 开始跳,每次可以跳 $[s,t]$ 的距离,给出一些石子的坐标,问从 $0$ 跳到或跳过 $L$ 最少踩几颗石子

题解

本题有多组数据。

HDU 5519

题意

给你包括 $0$ 的 $5$ 个数字,又告诉你每个数字的最多使用次数，问你由这 $5$ 个数字组成的不同 $n(n<=15000)$ 位数且无前导 $0$ 有多少个

题解

UVA 10304

题意

建二叉搜索树,二叉搜索树的花费就是每个节点的权值乘以它到根的距离(深度)的和,求最小的花费

题解

POJ 1160

题意

$n(n<=300)$ 个村庄,从中选 $p(p<=30)$ 个邮局，求每个村庄走到最近的邮局的距离和的最小值

题解

HDU 5951

题意

两个人竞标 $n(n<=255)$ 个物品，每个人初始金钱给定，一共 $n$ 轮，出价不同则价高者得，出价相同则奇数轮甲得，偶数轮乙得，两个人都会采取最优策略，问最后每个人会赢得几个物品。

题解

HDU 5807

题意

给定一个DAG图,点数为 $n(n<=50)$ 每个点有个权值 $w[i]$ ,给定初始 $3$ 个特工所在的位置是 $x,y,z$ 这 $3$ 个城市,每一时刻每个人都得移动到下一个城市,并且要求每一时刻两两之间都能联系当且仅当任意两个城市之间的权值差 $<=k$ ,求有多少种方案结束任务,共有 $q(q<=125000)$ 次询问

题解

POJ 2018

题意

给定一个正整数序列,找出一个区间使得平均值最大,要求该区间的长度大于等于 $F$

题解

HDU 5730

题意

给定一个数组 $a$ ,定义 $a[i]$ 表示连续 $i$ 个珍珠可以装饰的方案数,求 $n(n<=10^5)$ 个珍珠的项链可以装饰的方案总数

题解

$dp_i=\sum_{j=1}^{i}a_j*dp_{i-j}$ ,分治 $FFT$ 模板题

HDU 6078

题意

定义一种波浪数列,满足 $a_1<a_2>a_3<a_4>a_5...$ 给两个数列 $a,b$ ,选出 $a,b$ 的一个公共子串，且是一个波浪数列，问共有多少种方案. $a,b$ 的长度 $n,m<=2000$

题解

令 $dp[i][j][0/1]$ 表示以 $a[i],b[j]$ 为结尾的公共子列且在 $a[i],b[j]$ 处为波谷或波峰的总数,令 $sum[i][j][0/1]=\sum_{k=1}^{j-1}dp[k][j][0/1]$ ,则转移方程可写为 $dp[i][j][0]=\sum_{k=1}^{j-1}sum[i-1][k][1](b[k]>a[i])+1$ , $dp[i][j][1]=\sum_{k=1}^{j-1}sum[i-1][k][0](b[k]<a[i])$ ,在转移的过程中统计答案即可

BZOJ 4601

题意

$n×m(3<=n,m<=800)$ 的方格，每个格子有权值，求从左上角走到右下角的经过格子权值和的最大值。每次行动有限制，必须分为以下两步，先向任意一个方向走任意步（可以不动），再向任意一个方向必须走到边界（如果靠边界就可以不动）。

题解

LOJ 2268

题意

树形多重背包，每个点有 $a_i$ 个物品，每个价值为 $v_i$ ，体积都是 $1$ ，另外可以选择一条链，免费（即不算体积）选择链上所有点的物品各一个，求最大价值。 $n<=2*10^4,k<=5*10^5,nk<=25*10^6,v<=100$

题解