shyyhs

分类

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

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3897人学习

AtCoder思维大提升

6篇文章 750人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 840人学习

全部文章（共105篇）

[ZJOI2006]物流运输来自专栏

总体思路就是暴力,我们定义cost[i][j]表示第i天到第j天选择同一道路的花费(对于这个我们用起点跑个dij即可).好,下一步呢,我们不妨再设置一个状态f[i]表示到了第i天的最小花费是多少.它可以由<=的任何j转移过来.代码如下: #include <bits/stdc++.h&g...

最短路 DP

2020-10-15

5 771

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

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

树状数组 DP

2020-10-15

5 546

「StOI-1」小Z的旅行来自专栏

emmm..终于ac了,这里介绍一下标程做法,大佬的分治做法我也看不太懂,码风完全不一样.标程就是从后往前计算贡献,算出贡献的付出,最后保留的贡献就是f[n]. #include <bits/stdc++.h> typedef long long ll; const ll mod=998...

树状数组 DP

2020-10-08

5 687

C - Fair Elevator 来自专栏

代码注释很详细. #include <bits/stdc++.h> using namespace std; const int N=205; int vis[N];//-2表示前面有人,-1表示后面有人. bool f[N]; int main() { int n; s...

DP

2020-10-04

4 973

Number of Subsequences 来自专栏

首先令f[i][j]为到了第j个值为i的贡献. 我们很容易想到没有问号时候的转移方程. if(s[i]=='a') { f[0][i]=(f[0][i-1]+p[cnt])%mod; } if(s[i]=='b'...

DP

2020-09-28

6 683

[HAOI2008]硬币购物来自专栏

讲真的看到题,我都没想容斥原理...是我太菜了吗.首先拿个完全背包进行预处理.然后我们来观察下完全背包的含义.什么含义呢,就是你每个物品都任意取,在容量为x的情况下的方案数.假定我们对于其中的一个做出了限制,那么方案数会不会减少呢>?显然是会的,因为有限制嘛~会减少多少呢...其实假设我们只能...

容斥原理 DP

2020-09-24

4 679

[SCOI2009]游戏来自专栏

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

DP

2020-09-23

3 539

写诗来自专栏

一个简单的计数问题. #include <bits/stdc++.h> typedef long long ll; const ll N=5e3+5,M=30; const ll mod=1e9+7; ll s[N],c[N],f[N],g[N],st[M]; ll qp(ll a,ll...

DP 计数

2020-09-12

1 533

Discrete Centrifugal Jumps 来自专栏

这个题挺简单的(2333).首先我们想一个问题.假如这个题的算法是(单调栈+dp),那应该怎么做才能ac.单调栈无非就是维护一个单调序列,因为跳跃方式只有两种,如下图:而单调栈维护的是一种序列的单调性,我们很容易知道,假如我维护的序列是从后往前单调递减的,那么转移肯定只能在两个栈头和这个之间转移,同...

单调栈 DP

2020-09-09

1 840

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 540