lyyyyyy

DP

DAG图(1) 图论(4) 并查集(2) 搜索(3) 数学(8) 最小生成树(2) 未归档(22) 模板(18)

/ 注册

全部文章 / DP （共15篇）

cf Round 600 Antenna Coverage dp

Antenna Coverage 给定若n个区间,每次操作可以使一个区间左右拓宽1,求最小操作次数使得区间[1,m]均被覆盖. 考虑dp: dp[i]=区间[i,m]均被覆盖的最小花费转移: d ...

2019-11-17

0 422

单调队列dp

P3084 [USACO13OPEN]照片Photo 农夫约翰决定给站在一条线上的N(1 <= N <= 200,000)头奶牛制作一张全家福照片，N头奶牛编号1到N。于是约翰拍摄了M(1 <= M <= 100,000)张照片，每张照片都覆盖了连续一段奶牛：第i张照片中...

2019-10-24

0 471

波动序列 dp

P2467 [SDOI2010]地精部落题目描述传说很久以前，大地上居住着一种神秘的生物：地精。地精喜欢住在连绵不绝的山脉中。具体地说，一座长度为N的山脉H可分为从左到右的N段，每段有一个独一无二的高度Hi，其中Hi是1到N之间的正整数。如果一段山脉比所有与它相邻的山脉都高，则这段山脉是...

2019-10-24

0 575

概率dp Lights inside 3D Grid

Lights inside 3D Grid You are given a 3D grid, which has dimensions X, Y and Z. Each of the X x Y x Z cells contains a light. Initially all lights ar...

2019-10-22

0 416

概率dp Discovering Gold

Discovering Gold You are in a cave, a long cave! The cave can be represented by a 1 x N grid. Each cell of the cave can contain any amount of gold. I...

2019-10-22

0 452

期望dp A Dangerous Maze

A Dangerous Maze You are in a maze; seeing n doors in front of you in beginning. You can choose any door you like. The probability for choosing a doo...

2019-10-22

0 339

区间dp String painter

String painter Problem Description There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a p...

2019-10-22

0 407

多重背包的二进制优化

P4544 [USACO10NOV]购买饲料Buying Feed 约翰开车来到镇上，他要带KK吨饲料回家。运送饲料是需要花钱的，如果他的车上有XX吨饲料，每公里就要花费 X ...

2019-10-19

0 476

Football概率dp

POJ3071 Description Consider a single-elimination football tournament involving 2 ...

2019-10-02

0 430

区间dp

You Are the One The TV shows such as You Are the One has been very popular. In order to meet the need of boys who are still single, TJUT hold the sho...

2019-09-27

0 363