首页 > 其他分享 >「杂题乱刷」洛谷P2285

「杂题乱刷」洛谷P2285

时间:2023-12-08 10:03:11浏览次数:43  
标签:洛谷 int 杂题 IOS long 10010 P2285 define

题目传送门

一道小清新动态规划题,直接设 \(dp[i]\) 表示前 \(i\) 个鼹鼠最多能打到几个,然后状态转移方程也很好想了。

参考代码:

点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,ans,dp[10010],x[10010],y[10010],times[10010];
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
int main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>times[i]>>x[i]>>y[i];
	for(int i=1;i<=m;i++)
		dp[i]=1;
	for(int i=1;i<=m;i++)
		for(int j=1;j<i;j++)
			if(abs(x[i]-x[j])+abs(y[i]-y[j])<=abs(times[i]-times[j]))
				dp[i]=max(dp[i],dp[j]+1);
	for(int i=1;i<=m;i++)
		ans=max(ans,dp[i]);
	cout<<ans;
	QwQ;
}

标签:洛谷,int,杂题,IOS,long,10010,P2285,define
From: https://www.cnblogs.com/wangmarui/p/17884530.html

相关文章

  • 「杂题乱刷」洛谷P1064
    题目传送门一道算是dp的板子题了。题意大概就是01背包+捆绑。首先回顾一下01背包,一个比较基础的dp题,状态转移方程也很好想,是\(dp[i][j]=\max(dp[i][j],dp[i-1][j-w[i]]+v[i])\)。代码实现如下:点击查看代码#include<bits/stdc++.h>usingnamespacestd;longlo......
  • 杂题乱写 1
    用树剖补完了普及组OJ所有LCA的题DistanceQueries距离咨询POJ-1986翻译:FJ有\(N(2\leN\le40000)\)个农场,标号\(1\)到\(N\)。\(M(2\leM\le40000)\)条的不同的垂直或水平的道路连结着农场,道路的长度不超过\(1000\).这些农场的分布就像下面的地图一样,图中农场用\(F1\cdotsF7\)......
  • 洛谷 P1044 [NOIP2003 普及组] 栈 题解
    洛谷P1044[NOIP2003普及组]栈题解Sol本题通过分析可得:假设现在进行\(12\)次操作,我们把push认为是在地图上向右走,pop向上走,那么其中一个合法的步骤可以是(\(p1\)代表push,\(p2\)代表pop):\(p1,p1,p2,p1,p2,p2,p1,p1,p2,p2,p1,p2\)。而且我们发现,他最终会......
  • 网络流杂题
    一道一道记太浪费文章篇数了。先记几种dinic的复杂度。一般网络:\(O(n^2m)\)各边容量为\(1\)的网络:\(O(m\min\{m^{\frac{1}{2}},n^{\frac{2}{3}}\})\)二分图:\(O(m\sqrtn)\)更详细的分析。最大流UVA10735混合图的欧拉回路存在欧拉回路的判断条件:每个点出度=入度......
  • 洛谷P1443 马的遍历(BFS广度优先搜索)
    这道题只要求输入最小步数即可,而且数据的个数较大,所以优先采用BFS(广度优先搜索):广度优先搜索,即以数据搜索的广度优先,换句话说就是每一次操作都将所有可能的结果存储下来,随后对数据进行下一步处理,注意是对每组数据都只进行一次处理,如果是一条路走到头,这就变成了深度优先搜索(DFS)。而基......
  • [洛谷P5966] [BZOJ4344] [POI2016] Hydrorozgrywka
    题解建出原图的圆方树。由于原图无重边,不妨把桥看作二元环建树,这样圆点只与方点直接相连。圆方树定某一圆点为根后,若点\(u\)是圆点,定义点\(u\)的子仙人掌为点\(u\)子树中的圆点在原图的导出子图,定义该子仙人掌的根为点\(u\);若点\(u\)是方点,定义点\(u\)的子仙人掌为点......
  • P1090 [NOI洛谷P2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
    可以用堆来实现,或者更简单一点的优先队列优先队列:#include<queue>priority_queue<int,vector<int>,greater<int>>q;因为每次合并后,最小的两个值都会更新,所以可以很好的利用优先队列内元素有序的特点,减少因反复排序带来的时间复杂度;一开始我用STL自带的排序sort,报了5个TLE,后来意......
  • 洛谷P5719 分类平均
    intmain(){ intn,k,add=0,abb=0; doublesum=0,cnt=0; cin>>n>>k; for(inti=1;i<=n;++i) if(i%k==0) { add++; sum+=i; } cout<<fixed<<setprecision(1)<<sum/add<<''; for(inti=1;i<=n;++i) if(i%k......
  • 堆和优先队列(洛谷P3378)
    1.优先队列解决:优先队列:头文件和定义:#include<queue>template<classT,classContainer=vector<T>,classCompare=less<typenameContainer::value_type>>classpriority_queue;可表达为以下形式:priority_queue<Type,Container,Functional>type:即数据的类型Co......
  • OI_problem 玛丽卡_洛谷P1186
    题意一个\(N\)个点\(M\)条边的带边权无向图,要求输出最小的\(V\)使得不管去掉哪一条边,都存在从\(1\)到\(n\)的路径使得边权和不超过\(V\)。思路感觉朴素不太好做,考虑二分。对于一个二分值,即要判断在关于这个值的生成图中,\(1\)和\(n\)在不在一个边双里。考......