shyyhs

题解

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

/ 注册

全部文章 / 题解（共57篇）

小M和天平来自专栏

对于这题来说,难点在于分析左右两边的天平.但是我们可以发现,把这个石头放负数边其实就是abs(j−x).{对于这题来说,难点在于分析左右两边的天平.但是我们可以发现,把这个石头放负数边其实就是abs(j-x).}对于这题来说,难点在于分析左右两边的天平.但是我们可以发现,把这个石头放负数边其实就是a...

DP

2021-01-05

5 1013

AT3673 [ARC085D] NRE 来自专栏

一句话妙~原题是要我们求下标从1到n.可以选择一些操作,让原本全是0的ai的区间[l,r]变成1,求ai和bi不同数量的min.咋一眼看似乎十分懵逼,接下来就是一个很巧妙的转化了.首先我们定义二元组(i,j)代表同一下标下第一个数是多少(0/1),第二个数是多少(0/1).然后我们就可以发现答案就是...

DP

2020-10-28

4 755

Camels and Bridge 来自专栏

这题也是拖欠了几天的...emmm 题目大意:你有n头骆驼,他们要过桥,桥呢,有m座有两个属性l,v,l是它的长度,v表示在这个长度下,你不能超过v的载重,你呢,必须.让你安排下他们的过桥顺序.假如它们能够过桥,就要算出你安排的第一头骆驼和最后一头骆驼的间距,否则的话,输出-1. 思路是这样滴....

DFS 二分 DP

2020-10-16

8 821

[ZJOI2006]物流运输来自专栏

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

最短路 DP

2020-10-15

5 780

「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 977

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 683

写诗来自专栏

一个简单的计数问题. #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 537

Discrete Centrifugal Jumps 来自专栏

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

单调栈 DP

2020-09-09

1 845