shyyhs

题解

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

/ 注册

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

错排&排列计数题解来自专栏

不要我为啥更这题,因为这种题,代码简单,思路简单.dp:先讲讲错排公式,D[1]=0,D[2]=1.这个是初始值.下面讲讲转移方程:D[i]=(n-1)*(D[i-1]+D[i-2]).考虑把第n个元素放到任意一个地方,那就有n-1种放法,假定我放的位子为k,那么我k就有两种放法,第一种是放到n的位...

dp 组合数学

2020-07-10

2 671

扑克牌题解. 来自专栏

说句实话,假如不认真再想想期望就是平均数,你会对期望很迷惑.因为dfs是从后往前的,我们要求的答案是dp[0][0][0][0][4][4]当成答案,我们考虑用后面状态来更新前面状态.对于普通的4种花色来说,假设我们现在的状态是dp[a][b][c][d][x][y].那么我们从什么转移到它呢?显然...

期望 DFS DP

2020-07-02

0 658

acwing 274. 移动服务题解来自专栏

看着数据范围直接dp即可,注意题意 #include <bits/stdc++.h> using namespace std; const int N=205; const int M=1005; int dp[M][N][N];//有个人到了第i个指命位子,另外两个分别在j k位子的最...

dp

2020-06-22

3 676

hh很久没更了,本人不更视频了,但是会认真写题解的来自专栏

这是一篇dp的题解.题目是acwing 273.分级.题目描述很简单哈.题目:给定长度为N的序列A，构造一个长度为N的序列B，满足：1、B非严格单调，即B1≤B2≤…≤BN或B1≥B2≥…≥BN。2、最小化 S=∑Ni=1|Ai−Bi|。只需要求出这个最小值S。输入格式第一行包含一个整数N。接下来N...

dp

2020-06-20

1 968

acwing 278题解来自专栏

具体b站 #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int a[105]; int f[N]; int main() { int n,m; cin>>n>>m;...

dp

2020-06-18

1 656

acwing 271题解来自专栏

具体b站: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=32; ll dp[N][N][N][N][N]; int s[7]; int main() { int k;...

dp

2020-06-18

1 658

acwing 272题解来自专栏

这题思路比较简单,提前是你得设出来状态. dp(i,j)表示以1~j以b[j]结尾最长公共上升子序列. 转移的条件肯定是a[i]==b[j]. 假如a[i]!=b[j].假如我现在的a[i]<b[j]那么这个a[i]一定不能通过bj转移.因为不满足递增. 假如a[i]>b[j]那么我的a...

dp

2020-06-18

1 656