DP文章列表
[luoguP2331] [SCOI2005]最大子矩阵（DP）
传送门 orz不会做。。。 一个好理解的做法（n^3*k）： 分n=1和n=2两种情况考虑。 n=1时，预处理出前缀和sum[]。 设f[i][j]为到达第i格，已经放了j个子矩阵的最大和， 那么每次...DP
[BZOJ3054] Rainbow的信号（考虑位运算 + DP？）
传送门 BZOJ没数据范围。。。 其实数据范围是这样的。。 前20%可以直接n^3暴力枚举每个区间 前40%可以考虑每一位，因为所有数每一位都是独立的，而和的期望=期望的和，那么可以枚举每一位，再枚举...DP
[BZOJ4506] [Usaco2016 Jan]Fort Moo（DP？）
传送门 总之可以先预处理出来每个位置最多往上延伸多少 枚举两行，看看夹在这两行中间的列最大能构成多大的矩形 可以看出，必须得在一个两行都没有X的区间才有可能构成最大的答案 那么可以把这些区间处理出来，...DP
[POJ2151]Check the difficulty of problems（概率DP）
传送门 每个队之间是独立的 f[i][j]表示当前队伍前i个题答对j个的概率 满足条件的概率 == 全部方案（除去答对0）的概率 不满足条件的概率（每个队伍答对1~n1） #include cstdi...DP,概率和期望
[BZOJ1419] Red is good（期望DP）
传送门 逆推 只不过顺序还是顺着的，思想是逆着的 f[i][j]表示还剩下i张红牌，j张黑牌的期望值 那么边界是 f[i][0]=i，因为只剩i张红牌 f[0][j]=0，只剩黑牌，显然直接停止最优 ...DP,概率和期望
[BZOJ4993||4990] [Usaco2017 Feb]Why Did the Cow Cross the Road II（DP + 线段树）
传送门 f[i][j]表示当前第i个，且最后一个位置连接到j 第一维可以省去，能连边的点可以预处理出来，dp可以用线段树优化 #include cstdio#include iostream#incl...DP,线段树
[POJ2778]DNA Sequence（AC自动机 + DP + 矩阵优化）
传送门 AC自动机加DP就不说了 注意到 m = 10，所以模式串很少。 而 n 很大就需要 log 的算法，很容易想到矩阵。 但是该怎么构建？ 还是矩阵 A(i,j) = ∑A(i,k) * A(k...DP,AC自动机,矩阵
[TyvjP1519] 博彩游戏（AC自动机 + DP）
传送门 和bzoj1030一个德性 #include queue#include cstdio#include cstring#define N 500001#define LL long longi...DP,AC自动机
[BZOJ2287]【POJ Challenge】消失之物（DP）
传送门 f[i][j]表示前i个物品，容量为j的方案数 c[i][j]表示不选第i个物品，容量为j的方案数 两个数组都可以压缩到一维 那么f[i][j] = f[i 1][j] + f[i 1][j ...DP
[BZOJ1578] [Usaco2009 Feb]Stock Market 股票市场（DP）
传送门 可以看出 第一天买，第三天卖 == 第一天买，第二天卖完再买，第三天卖 所以我们只考虑前一天买，后一天卖即可 那么有按天数来划分 f[i][j]表示前i天，共有j元，最大的盈利 第一维可以省去...DP
共13页/121条 首页 上一页 6 7 8 9 10 11 12 13 下一页 末页
香港服务器 数据安全 数据库 美国服务器 云服务器 IT DDoS Linux Windows 虚拟化