蒟蒟独行

dp

01分数规划(1) AC自动机(2) bbp(1) cf(8) FFT(4) fleury(1) floyd(1) k-d树(1) kmp(1) kruskal重构树(1) lca(4) main(1) manacher(2) markdown(1) st表(1) trie(1) 一中(4) 主席树(1) 二分(2) 前缀和(1) 单调队列(1) 博弈论(3) 卡常(1) 双联通分量(5) 图论(1) 左偏树(1) 并查集(1) 强联通(2) 思维(11) 感想(6) 扫描线(1) 找规律(1) 技巧(1) 拓扑排序(2) 搜索(7) 数位dp(3) 数学(25) 斜率优化dp(1) 暴力(1) 最小树形图(1) 最短路(2) 未归档(1) 杂(15) 树(5) 树套树(2) 树形dp(4) 树状数组(5) 概率dp(1) 模拟(14) 模拟赛(2) 模板(30) 欧拉函数(1) 点分治(1) 状压dp(1) 生成树计数(1) 离散化(1) 算法复习(14) 线段树(20) 线段树合并(1) 网络流(2) 置换群(1) 虚树(1) 计算几何(1) 贪心(12) 轮廓线dp(1) 高斯消元(1) 高精度(2)

/ 注册

全部文章 / dp （共35篇）

洛谷P1373 小a和uim之大逃离

题目题解： f[i][j][t][p]表示当前是p在走，走到(i,j)这格两人魔瓶内的魔液的差的绝对值为t的方案数初值：f[i][j][x][0]=1，x为当前这个的魔液数量状态转移方程： f[i][j][t][0]+=f[i-1][j][(t-x+k)%k][1]+f[i][j-1...

2020-01-21

0 426

洛谷P1220 关路灯

题目题解：易证：在某一时刻，关的路灯一定是连续的。 f[i][j][t]表示已经关了i….j的路灯，当前在i或j的最小功耗(t=0表示在i，t=1表示在j) 初始化：除了f[k][k][0,1]=0外，其他所有f[i][i][t]=inf 状态转移方程： t=s[n]-s[j]+s[...

2020-01-21

0 567

洛谷P1156 垃圾陷阱

题目题解： f[i][j]表示用了前i个垃圾，垫高j的高度后，还能存活的时间（注意：不是总共能存活的时间）初始化：f[0][0]=10，其他都是负无穷状态转移方程： 1.吃垃圾 f[i][j]=max(f[i][j],f[i-1][j]-a[i].T+a[i-1].T+a[i].F)...

2020-01-21

0 391

洛谷P1273 有线电视网

题目题解： f[t][j]表示i连接j个用户的费用（可能是负数）初始化：f[i][0]=0，其他为负无穷状态转移方程： 1.t为用户 f[t][1]=mon[t-n+m] 2.t不为用户 f[t][j]=max(f[t][j],f[t][j-k]+f[e[i].to][k]-e[i...

2020-01-21

0 373

bzoj1057: [ZJOI2007]棋盘制作

题目题解： step1: 对于图上所有的棋盘一定属于以下两种类型： 1.黑格行列奇偶性相同，白格不同 2.白格行列奇偶性相同，黑格不同在输入的时候属于第一种情况的赋1，属于第二种情况的赋0 问题就转化成统计最大的1或0矩形和正方形 step2: 正方形： g1[i][j]表示...

2020-01-21

0 406

bzoj1899: [ZJOI2004]Lunch 午餐

题目题解：有一个贪心策略：吃饭时间越长的越早打饭然后动规，f[i][j]表示前i-1个数，第一个队列恰好要j的时间的最晚集合时间可以降维，把i去掉初始化：f[0]=0，其余为正无穷第一个窗口打饭： f[j]=min(f[j],max(f[j-x],j+y)) (x<=...

2020-01-21

0 383

洛谷P1070 道路游戏

题目题解： f[i]表示到i的时间，小新所得到的金币数状态转移方程：f[i]=max(f[i],f[i-k]-b[la]+sum) 标程： #include<bits/stdc++.h> using namespace std; int n,m,p,ans=(int)-1e...

2020-01-21

0 399

bzoj1801: [Ahoi2009]chess 中国象棋

题目某大佬的题解以下内容改编自大佬的题解题解： dp[i][j][k]表示在前i行中有j列已经有2个，有k列已经有1个，那么0的个数就是m-j-k个不放：直接加上dp[i-1][j][k] 放一个：1.把一列0变成1；2.把一列1变成2 放两个：1.把两列0变成1；2.把两列1...

2020-01-21

0 342

洛谷P3959 宝藏

有些人用模拟退火做，我一脸懵逼，于是还是老老实实用状压dp做吧。题目题解： f[x],dis[i]表示选点的状态为x，第i个点距离为dis[i]的最优答案记忆化搜索标程： #include<bits/stdc++.h> using namespace std; int...

2020-01-21

0 433

单调队列

修剪草坪（mowlawn）旅行（travel）产品（product） patrik(patrik.pas) 股票交易（trade 2秒） poj2559 Largest Rectangle in a Histogram BZOJ 1012 最大数m...

2020-01-21

0 535