瑜画

题解

/ 注册

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

树上子链题解

刚学树形dp表示WA哭了，调了半天才调出来。树的直径：对于一颗n个结点的无根树，找到一条最长路径，也就是找到两个点，让他们的距离最远。学习树形dp之前，有一个操作，就是通过第一次dfs找到一个最深叶子结点，再通过这个点为根，去找另一个最深的叶子结点，就完成了最长链的操作，这个方法虽然简单，但是不够...

dp

2020-08-07

0 724

没有上司的舞会题解

不懂树形dp的先看这里，已经会了的大神直接略过。。。最大独立子集最大独立子集的定义是，对于一个树形结构，所有的孩子和他们的父亲存在排斥，也就是如果选取了某个节点，那么会导致不能选取这个节点的所有孩子节点。有向图和无向图是大同小异的，介于本题是有向图，直接简单的叙述有向图的最大独立子集。首先，全局数组...

dp

2020-08-07

3 659

小G有一个大树题解

初学树形dp，看着雨聚聚的PPT上思路搞出来了。。。题目意思：找到一个割点，树将被割成两个部分，找到最大的连通块。状态转移方程：F[i]=max(max(tot[k]),n-tot[i]] （k是i的子树）然后dfs的时候把状态转移方程带进去就好了，注意每一次都得把自己这个点算上。另外，为了防止对...

dp

2020-08-07

4 955

拦截导弹题解

本题要求的是一个最大不增子序列长度和一个最大递增子序列的长度。关于这两个问题的求解，过于经典不再赘述。问题的关键是第二个问题是如何转化而来的。第二个问题是通过Dilworth定理得到的。引入两个离散数学的概念：链（chain）是一个偏序集S的全序子集（所谓全序是指任意两个元素可比较）反链...

dp

2020-06-13

0 788

合唱队列题解

首先看到题目，乍一眼以为是LIS模板题，后来发现他是一个先递增后递减的序列。那么可以把最大的那个数揪出来，然后左右划分，左边为一个正常的最长递增子序列，右边为一个倒过来的最长递增子序列。然后只要序列中每个数为中心，然后取最大的一种情况就好了。由于题目要求的是最少请几个人出去，那么就用总人数减去最大的...

dp

2020-06-12

0 683

迷雾森林题解

一道常规的dp题，注意位于最后一行和位于第一列dp需要特判，然后如果是不能走的地方，就让dp[]=0 #include <bits/stdc++.h> using namespace std; const int mod=2333; template<class T>inli...

dp

2020-06-12

0 630

过河题解

状态转移方程非常简单，dp[i]=min(dp[i],dp[j]+b[i])然而L高达10的9次方，但是石头的个数只有最多100个，有效的石头数目很少，但是他们分布的空间很广，符合离散化的特点，所以这道题是离散化dp 首先，这道题没有说石头的位置是按顺序输入的，所以要先对石头进行升序排序。接下来就进...

dp

2020-06-12

3 709

传球游戏题解

问题：n个人围成一个圈，从第一个人传球m次，每次能传给相邻的人，问有多少种方法经过m次传回给第一个人。思考：在第m次的时候传至第一个人手里，那么在m-1次的时候在第二个人或最后一个人手里。用dp[i][j]表示第j次传球，传到第i个人手里的情况有多少种。从而得到状态转移方程：dp[i][j]=dp[...

dp

2020-06-10

2 761

Rabbit的工作（1）题解

用一个二维数组dp[i][j]来表示工作i天，连续工作j天那么得到状态转移方程dp[i][j]=(dp[i-1][j-1])+j （如果当前字符为'1'）最终只要遍历dp数组，找到最长天数ans（并且它满足dp[i][j]<=K，即题目中说的总体力消耗不超过K） #include <bi...

dp

2020-06-10

0 752

CSL分苹果题解

将问题转化为wavator拿的苹果质量尽可能多，则变成一个容量为sum>>1的背包问题。由于题目要求的是质量尽可能多，那么w[i]等价于v[i]套用01背包模板，注意dp数组的大小至少要开到sum>>1 #include <bits/stdc++.h> using...

dp

2020-06-10

0 1018