秘密袭击 [BZOJ5250] [树形DP]
分析：听说正解是FFT+线段树合并，然而我并不会...我们来思考其他的方法。我们要求的是连通块第k大的和对于某一个连通块，对答案的贡献=val(Rank.K)我们不好直接算出每个连通块的Rank.K是多少但我们可以枚举一个limit for 1->w ，Σ(val(Rank.K)>=li...
HDU-1466 计算直线的交点数 经典dp
1、HDU-1466 计算直线的交点数2、链接：http://acm.hdu.edu.cn/showproblem.php?pid=14663、总结：不会推这个，看了题解。。状态转移： m条直线方案数=(m-r)条平行直线与r条直线相交数+r条直线自身方案数#include<iostrea...
HDU 2829 Lawrence(四边形优化DP O（n^2）)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2829题目大意：有一段铁路有n个站，每个站可以往其他站运送粮草，现在要炸掉m条路使得粮草补给最小，粮草补给的公式是将每个站能收到的粮草的总和。4----5-----1-----2粮草总和为4*5 + 4*...
Codeforces Beta Round #6 (Div. 2 Only) D. Lizards and Basements 2 dp
题目链接：http://codeforces.com/problemset/problem/6/DD. Lizards and Basements 2time limit per test2 secondsmemory limit per test64 megabytes#### 问题描述> ...
Light OJ 1031 - Easy Game(区间dp）
题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1031题目大意：两个选手，轮流可以从数组的任意一端取值， 每次可以去任意个但仅限在一端， 他们的得分分别是取得所有值的和。现在求这两个选手得分差值的最大值。解题思路：设dp[i][...
codeforce 337D Book of Evil ----树形DP&bfs&树的直径
比较经典的老题题目意思：给你一颗节点数为n的树，然后其中m个特殊点，再给你一个值d，问你在树中有多少个点到这m个点的距离都不大于d。这题的写法有点像树的直径求法，先随便选择一个点（姑且设为点1）来遍历一遍树，存下所有点到点1的距离。然后在m个特殊点中找到距离点1最远的点a1.然后以a1为初始点遍历一...
UVA - 1625 Color Length[序列DP 提前计算代价]
UVA - 1625Color Length白书很明显f[i][j]表示第一个取到i第二个取到j的代价问题在于代价的计算，并不知道每种颜色的开始和结束和模拟赛那道环形DP很想，计算这次转移会给其他的元素带来的代价，也就是转移前已经出现但还没结束的元素都会代价+1预处理每种颜色在两个序列中出现的位置b...
BZOJ 2302: [HAOI2011]Problem c( dp )
dp(i, j)表示从i~N中为j个人选定的方案数, 状态转移就考虑选多少人为i编号, 然后从i+1的方案数算过来就可以了. 时间复杂度O(TN^2)---------------------------------------------------------------------#inclu...
dp优化
入口A(fzu 1894)普通的单调队列,trick是进队判断的符号选取(>=wa , >ac).B(poj 2823)没什么好说的 ,坑爹poj g++,tle;c++,ac.C(hdu 3415)尝试封装了一下单调队列。。。感觉也没有方便多少. #define maxn 100010...
[HAOI2018]奇怪的背包 （DP，数论）
[HAOI2018]奇怪的背包$ solution: $首先，这一道题目的描述很像完全背包，但它所说的背包总重量是在模P意义下的，所以肯定会用到数论。我们先分析一下，每一个物品可以放无数次，可以达到的背包重量其实就是所有 $ gcd(a[i],P) $ 的倍数。 这一点和天天爱跑步简直神似！因为天天...
【dp】 poj 1157
不错的dp入门题 画出dp矩阵 每个dp【i】【j】是由“其上”的状态或是“其左上”的状态转化而来，那我们选对角线和上边进行三角dp推导#include<stdio.h>#include <iostream>using namespace std;#define MAX ...
HDU 1074 Doing Homework(像缩进DP）
Problem DescriptionIgnatius has just come back school from the 30th ACM/ICPC. Now he has a lot of homework to do. Every teacher gives him a deadline o...
uva 10817 - Headmaster's Headache ( 状态压缩dp)
本文出自 http://blog.csdn.net/shuangde800 题目链接： 点击打开链接题目大意某校有n个教师和m个求职者，已知每人的工资和能教的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘。思路这题不太好想,搞了很久。。f[s1][s2]： s1表...
dp练习（8）——数的划分
1039 数的划分 2001年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold ...
背包例题【dp练习】
ssl2289-庆功会 Description 为了庆贺班级在校运动会上取得第一名的成绩，班主任决定开一场庆功会，为此拔款购买奖品奖励运动员，期望拔款金额能购买最大价值的奖品，可以补充他们的精力和体力。Input 第一行二个数n(n<=500)，m(m<=5000)，其中n代表希望购买的...
Most Powerful（ZOJ 3471状压dp）
题意：n个原子，两两相撞其中一个消失，产生能量，给出任意两原子相撞能产生的能量，求能产生的最大能量。分析：dp[i]表示情况为i时产生的最大能量/*#include <map>#include <set>#include <list>#include <cm...
【树形dp练习】Y
题面 对于给定的树T，计算集合{A，B，C}的数量，其中：1、A，B，C是树T的节点2、不存在经过A，B，C的简单路径 分析 我猜题目叫Y的原因是因为要求的三个点构成一个Y的形状qvq 先看这个粉色的部分，考虑怎么计算第二部分的答案呢？ 根据组合数学的思想，可以从3,4,8为根的子树内选两个（一个...
简单的数位dp练习
【BZOJ1833】【ZJOI2010】数字计数 Description 给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 Input 输入文件中仅包含一行两个整数a、b，含义如上所述。 Output 输出文件中包含一行10个整数，分别表示0-9在[a,...
Android px、dp、sp之间相互转换 系统默认12 sp
px 就是像素sp=dpX字体比例（1.25f）一、dp（或者dip device independent pixels）一种基于屏幕密度的抽象单位。在每英寸160点的显示器上，1dp=1px。不同设备有不同的显示效果，这个和设备硬件有关。android里的代码如下：<span style=...
#DP# ----- OpenJudge山区建小学
没有记性。到DP不得不写博了，三天后又忘的干干净净。DP是啥 :-)一道久到不能再久的题了。OpenJudge 7624:山区建小学总时间限制: 1000ms 内存限制: 65536kB描述*在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过...