shyyhs

DP专题

图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

全部文章 / DP专题（共52篇）

Garland 来自专栏

= - =又是一个新东西,不合法的可以直接转移...dp还是简单 #include <bits/stdc++.h> using namespace std; const int N=105; int a[N]; int f[N][N][2];//到了第i个没填j个偶数数这个点填奇数/偶数...

DP

2020-08-05

2 540

能量项链来自专栏

这题是区间dp的经典题目,和石子合并一样,但是我忘了石子合并了,毕竟我是当自己大一啥都没学,只是接触过,现在重学来的~..说实话,因为解除了许多区间dp,但是以前对于有环的只知道×2,然后是用小区间更新大区间,但是一直没理解过它们,以至于简单的区间dp都没写出来,丢人...(主要是主观意识太强了,不...

DP

2020-08-05

1 545

没有上司的舞会来自专栏

都是基础啊,因为我也才刚学.凡是涉及树形dp,你就得先知道怎么转移.一般dp问题是解决max/min.那么这个dp问题也是解决max和min,但是怎么解决呢?很容易想到这个dp的表示方式.开两维:dp[u][0/1]表示以u为根节点的子树,选不选u节点所获得的最大权值,然后配合dfs更新子树信息转移...

DP

2020-08-04

1 559

二叉苹果树来自专栏

因为是枚举的每个分支,就是不可能在一个分支没选完就选第二个分支,然后转移就很合理了.就是两个分支可以看成01背包,然后保留多少个可以看成背包容量..就没了 #include <bits/stdc++.h> using namespace std; const int N=105; str...

DP

2020-08-04

1 665

Caesar's Legions 来自专栏

挺简单的一个dp..适合练手 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e8; ll dp[205][105][12][12];//到了第i个第一种分配了l个第一种连...

DP

2020-08-04

1 503

樱花来自专栏

二进制拆分题...没什么好说的,证明看上篇博客/.. #include <bits/stdc++.h> using namespace std; const int N=1e4+5,M=3e5+4e4; int t[N],c[N],p[N]; int id,n; int T[M],val...

DP

2020-08-03

1 545

关于背包二进制分解来自专栏

因为任何数都可以用二进制表示,在你的价值里面..然后最后一堆可以放一起的原因是前面可以表示任何数了,最后一堆无非就是填充最后一个1.举个栗子.假设我有个数10101010,很显然的一个结论10000000>1000000+100000+10000+1000+100+1.然后我主位的那个1肯定是...

DP

2020-08-03

3 557

Vladik and Memorable Trip 来自专栏

cf的每个dp题,都有它的特点吧,这个dp就很有特点,但是不难,也没什么好说的..代码如下: #include <bits/stdc++.h> using namespace std; const int N=5e3+5; int dp[N],a[N],w[N],e[N]; bool ...

DP

2020-08-03

1 514

k-Tree 来自专栏

ll dp[N][N][2];//深度i 总权值为j 是不是存在权值大于d的边..然后随便转移就好了... #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; c...

DP

2020-08-02

0 564

Word Cut 来自专栏

一道cf的dp题,也挺好的,虽然没牛客难..牛客还是牛/..这题是可以选择单词断开然后连起来,类似环.考虑dp,令dp[0][i]为操作i次是原串的方案数,dp[1][i]为操作i次是其他串的方案数.然后显然就有两个dp方程. dp[0][i]=dp[1][i-1]*(n-1). dp[1][i]=...

DP

2020-08-02

1 730