- 2024-07-16AT_dp_a Frog 1 题解
Frog1题面翻译NNN个石头,编号为1,2
- 2024-03-02AT_dp_z Frog 3 题解
这题的朴素dp是显然的。令\(dp_i\)表示跳到第\(i\)个石头的最小花费,有转移方程:\[dp_i=\min_{j=1}^{i-1}\{dp_j+(h_i-h_j)^2+C\}\]直接转移是\(O(n^2)\)的,考虑优化。首先对于\(\min\)以内的式子化简,得:\[dp_j+h_i^2+h_j^2-2h_ih_j+C\]将与\(j\)无关的项剔除,得:\[d
- 2023-12-24B - Frog 2
因为k很小,所以无需优化dp#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ intn,k; cin>>n>>k; vector<int>a(n+1); vector<int>dp(n+1,1e18); dp[1]=0; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=2;i<=n;i++){ fo
- 2023-12-24A - Frog 1
很好想的线性p#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ intn; cin>>n; vector<int>a(n+1); vector<int>dp(n+1,1e18); dp[1]=0; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=2;i<=n;i++){ dp[i]=min(dp[i],dp[i
- 2023-08-25CF605B的题解
算是对Leap_Frog大佬的补充吧qwq。%%%Leap_Frog.我们来看一下大佬的这段话:考虑倒着思考Kruskal算法。按边权从小到大排序。每次插入一条边。如果是树边,那就新开节点。否则在当前节点内任意连边。这样构造,每次非树边插入都比当前两端小。所以必然正确。对于“如果是
- 2023-08-17《Java编程思想第四版》学习笔记14
//:Frog.java//TestingfinalizewithinheritanceclassDoBaseFinalization{publicstaticbooleanflag=false;}classCharacteristic{Strings;Characteristic(Stringc){s=c;out.println("Creating
- 2023-07-20Frog 3 题解
Frog3题目大意题意都这么明确了还要这个干什么。存在\(n\)个点,每个点有一个属性\(h_i\),\(h_i\)单增,从点\(i\)移动到点\(j(j>i)\)的代价是\((h_i-h_j)^2+C\),其中\(C\)是给定的常数,求从点\(1\)移动到点\(n\)的最小代价。思路分析斜率优化DP板题。设\(f_i\)
- 2023-02-16【算法】青蛙从河边跳到对岸,河中需要依次落满树叶
Codility中有这样一个算法题,是说一只青蛙从河边(position=0)跳到河的对面去(position:x+1),河边有棵树,会在不同的时间点(以秒计算)落下树叶在河面上,我们需要保证河
- 2023-01-11Frog Jump II
FrogJumpIIYouaregivena0-indexedintegerarray stones sortedinstrictlyincreasingorderrepresentingthepositionsofstonesinariver.Afrog,init
- 2022-12-23青蛙过河算法
Asmallfrogwantstogettotheothersideofariver.Thefrogisinitiallylocatedononebankoftheriver(position0)andwantstogettotheoppositeba
- 2022-12-05Counting Elements - FrogRiverOne
QuestionAsmallfrogwantstogettotheothersideofariver.Thefrogisinitiallylocatedononebankoftheriver(position0)andwantstogettotheop
- 2022-12-01Time Complexity - FrogJmp
QuestionAsmallfrogwantstogettotheothersideoftheroad.ThefrogiscurrentlylocatedatpositionXandwantstogettoapositiongreaterthanoreq
- 2022-11-09HDU 3355 Hop — Don’t Walk!
ProblemDescriptionKERMITTHEFROGisaclassicvideogamewithasimplecontrolandobjectivebutrequiresagooddealofthinking.Youcontrolanani
- 2022-10-30【XSY3473】Frog(min25筛)
一些记号:记\(\mathbb{P}\)为质数集,\(p_i\)表示第\(i\)个质数。记\(\operatorname{lpf}(x)\)表示\(x\)的最小质因数为第几个质数。特别地,令\(\operatorname{l
- 2022-10-06LeetCode 1419. Minimum Number of Frogs Croaking
原题链接在这里:https://leetcode.com/problems/minimum-number-of-frogs-croaking/题目:Youaregiventhestring croakOfFrogs,whichrepresentsacombinationofth