1 穷源溯流

尚未进行身份认证

我要认证

路很长,尽管走便是。

等级
TA的排名 9k+

暑假日记

最近这几天事事特别多,看起来都是一些不慌不忙的小事,可是心里总是惦记着今天有练习了一下区间 DP感觉还是套路多一点有一个题还是挺有意思的有一个长度为 n 的数列,每次只能取走最左边的数或最右边的数,取走后将其乘以 i 加到答案上,i 为这是第几次取数问最后答案最大是多少这个题好像之前做过,挺有印象的状态方程也比较容易:dp[i][j]=max(dp[i+1][j]+a[i]*cnt,dp[i][j-1]+a[j]*cnt)借助区间 DP这个 dp 方程的意义比较特殊,只.

2020-08-11 22:22:43

HDU 1300 Pearls(前缀和+DP)

#include<stdio.h>#define min(x,y) (x<y?x:y)int main(){ int dp[105],num[105],sum[105],pri[105],i,j,k,t,m,n; scanf("%d",&m); while(m!=0) { scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&am.

2020-08-11 22:07:31

1574:矩阵取数游戏

首先先算出 n 行中每一行的最值,相加即可对于每一行来说,在区间 [i,j] 中,dp[i][j]=max(dp[i+1][j]+a[i]*2^i,dp[i][j-1]+a[j]*2^i)在开始之前,首先要处理一下,将谁放在最后一位提取,因为每一个数都可以是最后一个被提取的当然在实现过程中需要用到高精度,但我不会啊(逃)下面的代码只能过 6 个点const int N=100+5; int n,m,t; int i,j,k; ll a[N][N]...

2020-08-11 16:17:07

1573:分离与合体

const int N=300+5; int n,m,t; int i,j,k; int a[N]; int dp[N][N]; int ans[N][N];//储存区间 i~j 上的分界点void print(int l,int r,int step,int cnt){ if(l>=r) return ; int mid=ans[l][r]; if(cnt==step){ printf("%d ",mi...

2020-08-11 15:07:23

暑假日记

今天和朋友出去吃了顿饭,互相抱怨了一下,也难怪我们看的太远了,大二将要开学,就觉得自己的未来就这样了,吐槽了一下高中那些破事。下午回来还是老老实实的看了下树形动态规划的

2020-08-10 22:40:44

C. Obtain The String(二分+思维)

有两个字符串 s,t现在可以从 s 中拿出任意多个字符,他们可以不是连续的,但是顺序不能变问经过多少次操作后才能得到 tint main(){ IOS; rush(){ string s,t; cin>>s>>t; vector<int> v[30]; for(i=0;s[i];i++){ int k=s[i]-'a'; ...

2020-08-09 16:10:44

POJ 3268 Silver Cow Party(SPFA)

有 n 个点 m 条单向边,起点为 x,问从每一个点 i 到 x 的距离 + 从 x 到 i 的距离最大是多少开始建一个有向图,再将有向图的起点与终点置换,两次以 x 为起点的 SPFA 即可const int M=1e5+5;const int N=1000+5; int n,m,t; int i,j,k; vector<Pair> E[M]; bool inq[N]; int d[N]; void init()...

2020-08-09 14:58:04

POJ 2387 Til the Cows Come Home(带 vector 的 SPFA)

const int N=1000+5; int n,m,t; int i,j,k; vector<Pair> E[N]; bool inq[N]; int d[N]; void init(){ for(i=0;i<N;i++) { E[i].clear(); inq[i]=0; d[i]=inf; }}void SPFA(int s){ queue...

2020-08-08 22:10:44

暑假日记

今天补了一下昨晚的 CF 。昨晚的比赛,题目难度没有那么大,但是感觉到了小马宝莉对我并不友好一上来先看的 C 题,想了近 20 分钟吧,有思路,可以做,打完了之后 ac 不了,忽然想到二分,又打了一遍,又 WA,然后回到 A 题,这时候比赛过去 30 分钟了吧,很慌A 题的没读明白,直接看着样例打的一晚上卡在 B 题上,B 题也不算难,但我没以为这个题会卡,没注意数据范围,直接暴力,然后 T,当时也不想 C 题了,一直优化,但是本质还是暴力,比赛还剩 15 分钟,熬不下去了,看了看 D 题,

2020-08-08 16:27:11

D - Rarity and New Dress(二维 DP)

题目大概是从 n*m 的图中,找出菱形,菱形的形状由相同字母组成的题目中 涂绿 的形状首先想到的就是递推,以 ch[i][j]=‘a’ 为例:以 [i][j] 为中心向上向下走,直到遇到不为 ‘a’ 的字符在以 [i][j] 为中心向左向右走,直到遇到不为 'a' 的字符取最小值作为以 ch[i][j] 为中心的贡献值dp[i][j]=min(l[i][j],r[i][j],u[i][j],d[i][j])dp[i][j]:以 ch[i][j] 为中心的贡献值...

2020-08-08 16:12:21

C - Pinkie Pie Eats Patty-cakes(二分+模拟)

const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; int pos[N]; int maxx; bool C(int x)//间隔为 x{ int s=1; for(int i=1;i<=n;i++){//枚举题目中 ai 的范围 if(a[i]){ int tmp=a[i]; for(int j=s;j<=n...

2020-08-08 14:30:03

B. Applejack and Storages(模拟)

有 n 条边,给出对应的长度,有 m 次询问,每次会 ‘+’:添加一根木棒,或 ‘-’:减少一根木棒,问是否可以组成一个正方形和一个长方形,这两个四边形不可以重合,减少时,保证一定拥有这种长度的木棒一开始以为是到水题,开始暴力,期间穿插了能想到的优化,但 T 到我怀疑人生后,发觉这个题不大对头,开始换思路超时代码:const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; map<i...

2020-08-08 09:15:25

SPFA 算法总结

回顾一下使用邻接表的 SPFA 的算法如上图所示:假设原点是 1 ,也就是说 1 在队列中将与 1 节点连接的节点放入队列中此时更新 d[2]=3 , d[3]=9 , d[4]=7 , d[5]=3将以上节点放入队列中此时队列里有 2,3,4,5 节点然后 2 出队,发现与 2 连接的有 3 号节点,更新 d[3]=5, 但是 3 节点在队列中,所以不再进行操作之后 3 号节点出队,与 3 号节点连接的只有 4 号节点,但此时 d[4]=7<9+4,选择不跟新..

2020-08-07 22:20:50

HDU 2544 最短路(Dijkstra || SPFA)

Dijkstra:Spfa:const int N=2e5+5; int n,m,t; int i,j,k; int head[N],all=0;//id,edge_num int d[N]; //点 i 到起点的距离 bool vis[N];struct Edge{ int to,next; int w;}G[N];void add(int u,int v,int w){ G[all].w=w; ...

2020-08-07 21:28:38

GYM 101147 E. Jumping(最短路径转化+spfa)

有 n 个点,每个点 i 都可以传送到 i+x,或 i-x 的位置(每个点必须满足在区间 [1,n] 上),求每个点 i 到达 n 的最小传送次数将 i -> i-x 转化为 起点为 i ,终点为 i-x,边权为 1 的路径,借助最短路径算法求解const int N=2e5+5; int n,m,t; int i,j,k; int head[N],all=0; int d[N]; //点 i 到起点的距离 bool vis[N]...

2020-08-07 16:06:14

HDU 2066 一个人的旅行(spfa)

假设 0 为虚拟起点,SPFA 求解即可const int N=1e4+5; int n,m,t; int i,j,k; int head[N],all=0; int d[N]; //点 i 到起点的距离 int cnt[N]; //点 i 的入队次数 bool vis[N];struct node{ int to,next; int w;}G[N];void add(int u,int v,int w){ ...

2020-08-07 14:16:18

POJ 3259 Wormholes(spfa 判断负环)

有 n 个点,m 条无向边,t 条有向边,判断图是否存在负环const int N=1e4+5; int n,m,t; int i,j,k; int head[N],all=0; int d[N]; //点 i 到起点的距离 int cnt[N]; //点 i 的入队次数 bool vis[N];struct node{ int to,next; int w;}G[N];void add(int u,int v,...

2020-08-07 11:29:12

暑假日记

上午看了一下 spfa 算法的优化,在练习的时候发现 dij 还可以优化,打算明天学习一下。关于今天的 dijkstra 和 spfa 算法,dijkstra 算法和 Prim 算法相似,维护 d 数组,d[i] 一般表示从原点到达 i 位置的最短距离,当然可以根据题目要求变通,只要弄懂贪心过程这里还是比较好理解的如上图所示:假设原点是 1,维护 d 数组,d[i] 表示 1~i 节点的最小距离首先初始化 d[i]=inf; d[1]=0找出距原点最近的点,d[2]=3然后更新

2020-08-06 21:17:21

HDU 2680 Choose the best route(dij)

有 n 个地点,有 m 个条路,以及终点 e给出 m 条路的起点和终点,以及路费再给出 q 个起始点,求到达 e 点最小花费默认起始点为 0 ,利用 dij 求解const int N=1000+5; int n,m,t; int i,j,k; int d[N]; int f[N][N]; bool vis[N];void Dijkstra(int s){ for(int i=0;i<=n;i++){ ...

2020-08-06 20:23:33

POJ 2253 Frogger(dij)

有两只青蛙,分别在第 1,2,个位子上,其他的位子都是石头,现在青蛙 1 出发找 2,但是他的体力有限,所以要求你寻找一条路径,使得能够到达 2 号点的最短路径 并且 相邻的两块石头的最大距离尽可能的短const int N=200+5; int n,m,t; int i,j,k; double d[N];//源点到任一点 i 的最长距离 double f[N][N]; bool vis[N];int x[N],y[N];double dis(i...

2020-08-06 18:03:13

查看更多

勋章 我的勋章
  • 签到王者
    签到王者
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取