hannibal_Iecter

DP

ac自动机(7) bitset(2) BSGS(1) dfs(3) ODT(1) splay(1) ST表(2) tarjan(2) 中途相遇法(1) 主席树(4) 二分图(1) 二叉树(1) 分块(1) 分治(3) 回文树(1) 多校(1) 字符串(1) 容斥(2) 平衡树(5) 并查集(1) 快速乘(1) 数学(9) 整体二分(1) 树链剖分(2) 模拟退火(2) 水题(1) 爬山算法(1) 矩阵快速幂(2) 线性基(1) 线段树(10) 编译器(2) 背包(2) 莫队(1) 计算几何(1) 随机数(1) 高精度(1)

/ 注册

全部文章 / DP （共19篇）

洛谷P2503 [HAOI2006]【模拟退火】

题目链接读题意读了一年。。题意是将n个数分成m组，将每个组的求一个sum。计算m个sum的方差。求最小的方差。思路：先考虑连续选m个分组求最小方差，很容易想到DP。 dp[i][j]表示前i个数分成j组最小的花费。状态转移就是 ...

2019-08-04

0 598

【ac自动机】【DP】

fold爷出的题，突然想起来了存个板子。。对串S讨论一下DP就行了 d p [ ...

2019-07-31

0 346

ZOJ - 3494【AC自动机+数位DP】

数据那么大肯定是数位DP呀。 DP状态很好分析出来，注意数位DP上判一下前导零的情况就行。 #include<bits/stdc++.h> using namespace std; const int maxn = 2005; typedef long long ll; char ss...

2019-04-11

0 272

HDU-2243考研路茫茫——单词情结【AC自动机+矩阵快速幂】

看到L那么大就应该想到矩阵快速幂。而且这道题和之前的POJ 2778. DNA Sequence很想。我们只需要计算一下长度小于等于n的不包含特殊串的个数（矩阵中要增加一维代表每一行的sum），然后用总的可能数减去不包含的就是答案了（总的可能数很多人都是用矩阵写的，其实用等比数列求和公式就行了啊...

2019-04-11

0 395

HDU-2457 DNA repair【AC自动机+DP】

第一次。。自己分析出来的dp。。。。。和之前做过的题很像，感觉有关构造字符串的题都有套路。 dp中一定包含一维trie图中的节点状态(好像是废话) 这道题我们用dp[i][j]表示长度为i节点状态为j最少消去的数量。状态转移就是dp[i][u] = min(dp[i][u], dp[i-1][j...

2019-04-10

0 425

Clannad 18四川省赛【AC自动机+DP】

题目链接第一次遇到卡last优化的题。因为要不断跳fail链上的ed节点，不用last优化的话会T。因为fail指针指向的是当前节点的最长后缀，所以用dp[i]表示前i个字符能分解的数量，转移方程就为 dp[i] += dp[i-size[u]] (u是fail链上的所有节点) 所以要last...

2019-04-09

0 519

UVA - 11825【状压DP】

题意很容易懂，注意一点相邻不代表联通。首先要知道有两种状态 1，第i台计算机影响的所有计算机的状态。(p[18]) 2，攻击哪些状态的计算机可以使服务瘫痪。(c[1<<18]) 使dp[s]代表使状态为s的计算机最大数量的服务瘫痪。(dp[1<<18]) 状态转...

2019-03-01

0 366

[Wc2008]游览计划【斯坦纳树】

斯坦纳树的问题模型是：有一个图，要求保留图中最少的边/最小的边权和使得某k个点相互连通。最小生成树是斯坦纳树的一种特殊情况。我们用f[i]][j][s]表示方格中i,j位置与各个景点之间的联通情况。如果景点数为3时，111表示全部联通， 101表示第二个景点没有联通。。。当然第x个景点的 f...

2019-02-28

0 444

poj3585【树形dp二次换根】

这道题如果用暴力的方法是枚举根节点，对每个根节点dfs下去，但是这样肯定会T，需要用树形dp优化一下。辅助数组：d[maxn], f[manx]; d[i]：代表以任意某个节点为根，i可以向其子节点流的最大流量。 f[i]：代表以i为根节点时，最大流量。当我们以1为根节点时，明显f[1] = d...

2019-02-28

0 465

P1896 [SCOI2005]【状压dp】

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5; int Case = 1; int n, m; ll y[...

2019-02-27

0 400