- 博客(9)
- 资源 (2)
- 收藏
- 关注
RSS订阅
原创 “Hello Word!“
按照老传统,第一篇博客发个Hello Word~#include <cstdio>using namespace std;int main(){ printf("Hello Word!"); return 0;}
2020-08-24 13:28:40
124
原创 [题解] CF724E Goods transportation
**[题解] CF724E Goods transportation**CF题目链接洛谷题目链接网络流做法:就是从源点 SSS 向每个城市 iii 连权值为 pip_ipi 的边，从城市 iii 向汇点 TTT 连权值为 sis_isi 的边，当i<ji<ji<j时从城市 iii 向城市 jjj 连权值为 ccc 的边，求最大流即可因为最大流等于最小割,所以考虑如何找最小割断开一个点连接原点和汇点的路径方案一:断开与原点 SSS 的边，同时也要断开连接其他编号比
2021-05-04 20:28:31
133
原创 [题解] P2120 [ZJOI2007]仓库建设 动态规划 斜率优化
[题解] P2120 [ZJOI2007]仓库建设洛谷题目链接首先考虑用动态规划f_ifi表示从第11个到第ii个位置 (第ii个位置修建仓库) 的代价sum_isumi表示从第11个到第ii个位置的成品总和dis_idisi表示到第ii个位置到到第nn个位置的距离s_isi表示从11个到第ii个位置所有成品运输到第nn个位置的代价可以列出转移方程f_i=min\{f_j+s_i-s_j-(sum_i-sum_j)*di...
2021-01-24 12:18:52
174
原创 [题解] P1073 最优贸易 SPFA 分层图
[题解] P1073 最优贸易 SPFA 分层图洛谷题目链接牛客题目链接本题在最短路的基础上,本题需要考虑在何时购买,何时卖出,因为只可以买入卖出1次,在每个位置时一共有三种情况:没有买入,买入但没有卖出,已经卖出,重点是其中的转换1.同状态之间转换 建一条长度为0的边2.没有买入->买入但没有卖出 建一条长度为负买入价值的边,表示买入3.买入但没有卖出->已经卖出 建一条长度为卖出价值的边,表示卖出然后就可以建立一个分层图,因为存在负边,所以用SPFA求解如
2020-09-12 19:25:01
157
原创 [题解] P2296 寻找道路 DFS/BFS 最短路
[题解] ]P2296 寻找道路 DFS/BFS 最短路洛谷题目链接牛客题目链接题目要求路径上的所有点的出边所指向的点都直接或间接与终点连通,我们可以先做一遍dfs找出那些点与终点联通,再依次判断每一个点所有出边所连节点是否有和终点不联通的,如果有那么这个节点不满足条件声明:c[i]表示节点i是否与终点联通,_c[i]表示节点i是否可以经过 (限于水平,数组的名字不太优美,是can的简写)求数组c的代码:void dfs(int u){ c[u]=1; for(int v=0.
2020-08-28 20:47:36
232
原创 [题解] P2758 编辑距离 线性DP
P2758 编辑距离 题解 洛谷题目链接 题目描述概括:A,B两个字符串,对A字符串进行删除/添加/修改字符操作,求A到B的最小操作次数本题可以用线性DP来解决,设f[i][j]表示字符串A的前i个字符变为字符串B的前j个字符的最少操作次数,状态转移时一共有两种情况:1.A[i]=B[j] 那么A的第i个字符和B的第j个字符正好对应,不需要修改,此时f[i][j]=f[i-1][j-1]if(s1[i-1]==s2[j-1])f[i][j]=f[i-1][j-1];2.A...
2020-08-24 13:59:42
787
原创 [题解] P1040 加分二叉树 区间DP
P1040 加分二叉树题解 这是本人第一次写题解,如有不足欢迎提出洛谷题目链接:https://www.luogu.com.cn/problem/P1040 这个题可以用区间DP来解决,因为加分计算为:subtree 的左子树的加分 *subtree 的右子树的加分+subtree 的根的分数,设f[i][j]表示区间[ij]代表子树的最大分值,可以写出以下转移方程 f[i][j]=max(f[i[k-1]*f[k+1][j]+f[k][k]) (i<=k<...
2020-08-21 14:52:22
200
Monitor.cpp
2021-03-06
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人