shyyhs

DP专题

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

/ 注册

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

シャッフル来自专栏

哥也会打日语= =.其实是复制的.对于这题来说.想到状态表示就不难了,f[i][j]状态表示是到了第i个分配好了i-1,剩下j个1的不同方案数.我们在末尾+'0',答案就是f[len][0]了.转移不是特别难,具体看注释.代码如下: #include <bits/stdc++.h> us...

DP

2020-11-04

3 673

格子刷油漆来自专栏

画图+手推公式.还是一道不错的题~.首先考虑从顶点开始全部遍历的三种走法.对于第一种和第三种,他们都走过去了,并不一定走回来.我们令其为a[],对于第二种而言,他们走过去了,又走回来了,我们令其为b[].对于第一种情况而言呢,每次都有选这个点还是选另外一个点,所以 a[i]+=2*a[i-1].对于...

DP

2020-11-03

3 669

AT2155 [ARC064D] Rotated Palindromes 来自专栏

妙~.千万不要因为数据大就害怕,得学会冷静分析...对于这题而言,我们要知道一件事,就是回文串和循环节之间的一个关系.首先回文串一定可以写成循环节的整数倍的形式).然后我们还得考虑一个移动过程,什么时候会重复.这里的话要分奇偶了.对于奇字符串而言:abaaba,假设循环节长度是len,那么移动len...

思维 DP

2020-10-29

4 715

[SCOI2014]方伯伯的玉米田来自专栏

emmm...我真的太懒了,老是拖欠,有些题写完就忘了,但尽管如此,我还是拖欠...这两天更是罪大恶极的打了两天LOL,呜呜呜.好了,废话就这么多. 这题是树状数组维护的dp,怎么维护呢.在维护dp前,我们必须要知道一个性质.什么性质呢,就是你选区间的时候鸭,区间的右端点一定是n(证明:因为假如不在...

树状数组 DP

2020-10-15

5 552

[SCOI2009]游戏来自专栏

很巧妙的变形...大概cf也有很多,这个题首先是一个排列的关系可能会形成1~n个环..然后就是问你环的大小的lcm,这个可以转化,我们知道lcm可以写成每个质因数的乘积.又有个巧妙的转化了,因为1的存在.我们可以任意分配质因子个数,这样是不影响方案数的(因为到了最后也最多这个值,其他值也会被包含)....

DP

2020-09-23

3 535

Longtail Hedgehog 来自专栏

一个水题,先统计下每个点的度数,然后维护一个数组表示到这个点的最大长度是多少.然后拿ans更新就好. #include <bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int>v[N]; int d...

DP

2020-09-08

1 547

圆形数字来自专栏

前导0一定要处理... //进阶指南dp挺好的,经典又不难...先把最后一题写完吧orz. #include <bits/stdc++.h> using namespace std; typedef long long ll; const int base=33; const int N...

DP

2020-08-26

2 593

饼干来自专栏

挺有价值的一个dp,记录一下.. //先分配最大的,然后枚举几个1dp即可 #include <bits/stdc++.h> using namespace std; const int N=5e3+5,M=35; int f[M][N];// int sum[N]; struct v...

DP

2020-08-20

1 576

I-区域来自专栏

有生之年,敲这么长的dp代码,记录一下~ //一题不会是真的. #include <bits/stdc++.h> using namespace std; //f(i,j,l,r,k1,k2)//到了第几行选了几个数选的数的左端点右端点是什么左端点是递增/递减右端点是递增/递减...

DP

2020-08-20

2 579

陪审团来自专栏

#include <bits/stdc++.h> using namespace std; const int base=400; int f[205][25][805]; int p[205],d[205]; int main() { int n,m,T=1; whil...

DP

2020-08-18

2 500