Best Cow Fences_二分&&DP
DescriptionFarmerJohn'sfarmconsistsofalongrowofN(1<=N<=100,000)fields.Eachfieldcontainsacertainnumberofcows,1<=ncows<=2000.FJwantstobuilda...
[vijos1892]树上的最大匹配（树形DP）
题目：https://vijos.org/p/1892分析：（100分其实用到各种c++优化，没什么实际意义，所以弄70就可以了）题目很简单，很容易想出用树形DP，但是求方案数的时候，满满都是细节……，本渣考试时候就跪了……只能膜拜神犇代码……#include<cstdio>#inclu...
划分数 (DP)
输入:n=4m=3M=10000输出:4(1+1+2=1+3=2+2=4)复杂度(nm)intn,m;inta[MAX];intdp[MAX][MAX];//数组voidsolve(){dp[][]=;for(inti=;i<=m;i++){for(intj=;j<=n;j++){if(...
POJ2533Longest Ordered Subsequence（DP）
http://poj.org/problem?id=2533在经典不过的DP题目了。。。。#include<map>#include<set>#include<stack>#include<queue>#include<cmath>#inc...
poj 1141 Brackets Sequence（区间DP）
题目:http://poj.org/problem?id=1141转载：http://blog.csdn.net/lijiecsu/article/details/7589877定义合法的括号序列如下：1空序列是一个合法的序列2如果S是合法的序列，则(S)和[S]也是合法的序列3如果A和B是合法的序...
HDU 4599 概率DP
先推出F(n)的公式：设dp[i]为已经投出连续i个相同的点数平均还要都多少次才能到达目标状态。则有递推式dp[i]=1/6*(1+dp[i+1])+5/6*(1+dp[1]).考虑当前这一次掷色子，有1/6的概率投的和前面的一样，有5/6的概率不一样，不一样就要重新投，就到了dp[1]的状态，这里...
HDU 5001 概率DP || 记忆化搜索
2014ACM/ICPCAsiaRegionalAnshanOnline给N个点，M条边组成的图，每一步能够从一个点走到相邻任一点，概率同样，问D步后没走到过每一个点的概率概率DP 測试数据太水了。。。。10000*50*50*50都能过加个vector优化到#include"stdio.h"#in...
POJ 2948 Martian Mining（DP）
题目链接题意：n×m的矩阵，每个格子中有两种矿石，第一种矿石的的收集站在最北，第二种矿石的收集站在最西，需要在格子上安装南向北的或东向西的传送带，但是每个格子中只能装一种传送带，求最多能采多少矿。思路：记忆化搜索。也可以用递推。//#include<stdio.h>#include<...
LightOJ1021 Painful Bases（状压DP）
容易想到状态dp[n][S][m]（S是数字出现的集合），表示前n位用了数字集S且模k余数是m的方案数。利用(xy)base%k=(x*base+y)%k=((x%k ) *base+y)%k，进行状态第三维的转移。不过d[16][216][20]有2000多W的状态数，且不说超时的问题，内存早已超...
C语言使用DP动态规划思想解最大K乘积与乘积最大问题
Dynamic Programming动态规划方法采用最优原则来建立用于计算最优解的递归式,并且考察每个最优决策序列中是否包含一个最优子序列,这里我们就来展示C语言使用DP动态规划思想解最大K乘积与乘积最大问题
Codeforces Round #274 Div.1 C Riding in a Lift --DP
题意：给定n个楼层，初始在a层，b层不可停留，每次选一个楼层x，当|x-now|<|x-b|且x!=now时可达（now表示当前位置），此时记录下x到序列中，走k步，最后问有多少种可能的数的序列.解法：定义： dp[i][j]表示第i步在j楼的不同序列的个数转移方程：当j<b时，那么...
BZOJ 2286 消耗战 (虚树+树形DP)
给出一个n节点的无向树，每条边都有一个边权，给出m个询问，每个询问询问ki个点，问切掉一些边后使得这些顶点无法与顶点1连接。最少的边权和是多少。(n<=250000,sigma(ki)<=500000)考虑树形DP，我们令mn[i]表示i节点无法与1节点相连切除的最小权值。显然有mn[i...
hdu 6170 Two strings dp
TwostringsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)ProblemDescriptionGivingtwostringsandyoushouldjudgeiftheyarematch...
HDU1565 方格取数(1)(状态压缩dp)
题目链接。分析：说这题是状态压缩dp，其实不是，怎么说呢，题目数据太水了，所以就过了。手动输入n=20的情况，超时。正解是网络流，不太会。A这题时有个细节错了，是dp[i][j]还是dp[i][q[j]]?答案是dp[i][j],因为q[j]必定会超（感谢CZ学长提示）。AC代码如下：#includ...
Dice (III) 概率dp
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;intt,n;doubledp[100010];intmain(){scan...
【BZOJ-1055】玩具取名 区间DP
1055:[HAOI2008]玩具取名TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 1560 Solved: 907[Submit][Status][Discuss]Description某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意...
Little Sub and Piggybank （杭师大第十二届校赛G题） DP
题目传送门题意：每天能往存钱罐加任意实数的钱，每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品，则可以买，求最后的最大快乐值。思路：先来一段来自出题人的题解：显然的贪心：如果第$i$天买完，准备在第$j$天买，那么显然最优是在$i+1$到j天放$wi/(j-i)$的钱。于是假定选...
湖南省第十二届大学生计算机程序设计竞赛 B 有向无环图 拓扑DP
1804:有向无环图TimeLimit: 5Sec MemoryLimit: 128MBSubmit: 187 Solved: 80[Submit][Status][WebBoard]DescriptionBobo有一个n个点，m条边的有向无环图（即对于任意点v，不存在从点v开始、点v结束的路径...
hdu 5569 matrix dp
matrixTimeLimit:20SecMemoryLimit:256MB题目连接http://acm.hdu.edu.cn/showproblem.php?pid=5569DescriptionGivenamatrixwithnrowsandmcolumns(n+misanoddnumber),...
POJ 3280 Cheapest Palindrome（DP 回文变形）
题目链接：http://poj.org/problem?id=3280题目大意：给定一个字符串，可以删除增加，每个操作都有代价，求出将字符串转换成回文串的最小代价SampleInput34abcba10001100b350700c200800SampleOutput900分析：这是一道最长回文串的变...