A12NCH3N-CSDN博客

原创 DP（最长上升子序列）——腾讯校招题：逛街

l[i]表示从左到右以楼i结尾的最长下降子序列的长度，在楼i往左看，看到最多的楼的数量就是l[i-1]r[i]表示同理，在楼i往右看，以楼i+1为起点的最长上升子序列的长度就是能看到最多的楼的数量。最后吧两个加起来并加上楼i自身的1，就是答案。#include<bits/stdc++.h>using namespace std;const int N=100010;int w[N],l[N],r[N];int main(){ int n; cin>>n; .

2022-04-22 00:06:35 453

原创 Dijkstra堆优化版模板

#include<bits/stdc++.h>using namespace std;const int N=40;int mp[N][N];int dist[N],st[N];int n,k;typedef pair<int,int> PII;void dijkstra(int kk){ memset(dist,0x3f,sizeof(dist)); priority_queue<PII,vector<PII>,greater&lt

2022-04-09 00:19:00 479

原创 SPFA模板题

#include<iostream>#include<cstring>#include<queue>using namespace std;const int N=1000010;int n,m,start,ed,idx;int e[N],h[N],ne[N],w[N];int dist[N],st[N];void add(int a,int b,int c){ e[idx]=b,w[idx]=c;ne[idx]=h[a],h[a]=idx+..

2022-04-08 20:31:34 561

原创 DP+DFS——最大值路径

dp算出最大值后，搜索所有路径，走到终点时的值等于最大值则方案数+1#include<iostream>using namespace std;const int N=20;int n,ans,maxn;int dp[N][N];int w[N][N];void dfs(int h,int l,int count){ if(h<1||l<1||h>n||l>n) return; if(count==maxn) {..

2022-04-08 14:16:25 391

原创 DP（01背包）+离散化——网格贪吃蛇

蓝桥杯试题算法提高网格贪吃蛇（C++）离散化的步骤：排序，去重得到的序列中元素的位置就是离散化后的坐标。例如(2,5) (1000,500) (1000, 999)先将所有数字放入数组中并排序去重得到：2,5,500,999,1000离散化后的坐标就是(1,2) (5,3) (5,4)该题中地图很大，无法开这么大的二维数组。但实际给出的点就1000个点，所以需要进行离散化。注意，虽然只有1000个点，但却有2000个数，所以N要定到2000以上。参考文章：#include&..

2022-04-07 23:13:28 623

原创状态机DP——秘密行动

0表示爬，1表示跳，不能连续跳2次，因此1的状态只能由0转移过来。#include<bits/stdc++.h>using namespace std;const int N=10010;int dp[N][2],w[N];int main(){ int n; cin>>n; for(int i=2;i<=n+1;i++) cin>>w[i]; //dp[0][0]=dp[0][1]=0; for.

2022-04-06 23:44:07 239

原创 DP——最大连续子序列的和

s 表示以 i-1 这个数为结尾的最大连续子序列的和。ans表示以 i 这个数为结尾的最大连续子序列的和。当s≤0，s+w[i]不会变大，因此舍弃前面的子序列和，s置零否则s加上当前数w[i]#include<bits/stdc++.h>using namespace std;const int N=100010;int w[N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++..

2022-04-06 23:32:47 197

原创自写全排列函数——递归实现排列型枚举

参考：全排列函数和自写排列#include<bits/stdc++.h>using namespace std;const int N=10;int a[]={1,2,3,4,5,6,7,8,9};int ans[N],st[N];int n;void dfs(int start,int ed){ if(start==ed) { for(int i=0;i<n;i++) cout<<ans[i]<.

2022-03-30 23:52:18 190

原创 DP——背包问题求具体方案

#include<bits/stdc++.h>using namespace std;const int N=1010;int v[N],w[N],dp[N][N];int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=n;i>0;i--) { ..

2022-03-29 21:43:34 159

原创 BFS（A*）——八数码

相当于滑块拼图游戏#include<bits/stdc++.h>using namespace std;int evaluate(string now){ int value=0; for(int i=0;i<now.size();i++) { if(now[i]!='x') { int t=now[i]-'1'; value+=abs(i/3-t/3)+abs(i%3-t..

2022-03-28 23:04:14 3933

原创 DP（多重背包问题）——庆功会

时间复杂度为O(nms)数据量为3kw无需优化#include<bits/stdc++.h>using namespace std;const int N=6010;int dp[N];int n,m;int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { int v,w,s; cin>>v>>w>>s; .

2022-03-28 00:41:37 355

原创 DP（01背包）——数字组合

二维数组：#include<bits/stdc++.h>using namespace std;const int N=110,M=10010;int dp[N][M];int a[N];int main(){ int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; dp[0][0]=1; for(int i=1;i<.

2022-03-27 21:33:18 123

原创 Dijkstra——最小花费

#include<bits/stdc++.h>using namespace std;const int N=2010;double g[N][N];double dist[N];int st[N];int n,m,a,b;void dijkstra(){ //memset(dist,0,sizeof(dist)); dist[a]=1; for(int i=1;i<=n;i++) { int t=-1; ..

2022-03-27 18:53:50 406

原创 BFS——山峰和山谷

#include<iostream>#include<algorithm>#include<queue>using namespace std;const int N=1010;typedef pair<int,int> PII;int mp[N][N],st[N][N];int n;int peak,valley;void bfs(int h,int l){ queue<PII> q; q.push({...

2022-03-27 14:03:25 557

原创单源最短路（用floyd算法）——信使

#include<bits/stdc++.h>using namespace std;int n,m;const int N=110;int dist[N][N];int main(){ memset(dist,0x3f,sizeof(dist)); cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b&g..

2022-03-26 00:11:53 382

原创 BFS——池塘计数

#include<bits/stdc++.h>using namespace std;#define x first#define y secondconst int N=1010;char mp[N][N];int ans=0;int n,m;typedef pair<int,int> PII;void bfs(int h,int l){ queue<PII> q; q.push({h,l}); mp[h][l]='.';.

2022-03-24 01:04:47 300

原创最小步数模型的BFS——魔板

#include<bits/stdc++.h>using namespace std;map<string,int> dist;map<string,pair<char,string> >pre;string moveA(string t){ reverse(t.begin(),t.end()); return t;}string moveB(string t){ string str=""; str+=t..

2022-03-21 13:43:09 186

原创计数DP——瓜瓜打游戏（EASY）

#include<bits/stdc++.h>using namespace std;const int N=5010;long long dp[N][N];//dp[i][j]代表过了i关获得j个徽章的路径数int m[N];int main(){ int n,p; cin>>n>>p; for(int i=1;i<=n;i++) cin>>m[i]; dp[0][0]=1; for.

2022-03-20 14:39:50 4300

原创筛质数——哥德巴赫猜想

#include<bits/stdc++.h>using namespace std;const int N=1000010;int primes[N],cnt;bool visited[N];//false为没有被筛掉，是质数。void get_primes(int n){ for(int i=2;i<=n;i++) { if(visited[i]==false) primes[cnt++]=i; for(int j=0;..

2022-03-18 19:51:11 212

原创拓扑DP——来自wzc的简单拓扑dp

#include<bits/stdc++.h>using namespace std;const int N=100010,M=200010;int n,m;int dp[N];int h[N],e[M],ne[M],v[N],idx;int d[N];void add(int a,int b){ e[++idx]=b; ne[idx]=h[a]; h[a]=idx;}void topsort(){ queue<int> que.

2022-03-18 17:04:53 382

原创拓扑排序（数组模拟邻接表）——家谱树

第一次用数组模拟单链表，注释和下图就是我的全部理解参考：数组模拟邻接表-头插法(C++)#include<bits/stdc++.h>using namespace std;const int N=110,M=N*N/2;int n;int h[N],e[M],ne[M],idx;/*h是表头数组，存储顶点i最后插入的一条边的序号。（注：这里采用头插法，这条边相当于使用邻接表时，位于该单链表的第一个结点）e是终点数组，存储i号边指向的顶点ne是指针数组，存储i号边指向的.

2022-03-18 14:22:55 678

原创 DP——二维费用的背包问题

#include<bits/stdc++.h>using namespace std;const int V=110,M=110;int dp[V][M];int main(){ int n,v,m; cin>>n>>v>>m; for(int i=1;i<=n;i++) { int a,b,c; cin>>a>>b>>c; f.

2022-03-17 16:18:21 135

原创 DP（二维花费01背包）——宠物小精灵之收服

#include<bits/stdc++.h>using namespace std;const int N=1010,M=510;int dp[N][M];int main(){ int n,m,k; cin>>n>>m>>k; for(int p=1;p<=k;p++) { int c1,c2; cin>>c1>>c2; for(in..

2022-03-16 17:59:13 188

原创 DP（01背包）——装箱问题

#include<bits/stdc++.h>using namespace std;const int N=20010;int dp[N],m[N];int main(){ int v,n; cin>>v>>n; for(int i=1;i<=n;i++) { int k; cin>>k; for(int j=v;j>=k;j--) .

2022-03-16 16:57:16 296

原创 DP（01背包）——采药

#include<bits/stdc++.h>using namespace std;const int N=1010;int dp[N];int main(){ int T,M; cin>>T>>M; for(int i=1;i<=M;i++) { int t,v; cin>>t>>v; for(int j=T;j>=t;j--) .

2022-03-16 16:33:56 842

原创 DP（最长上升子序列）——拦截导弹

求最少配备的系统数等价于求最长不上升子序列的最少个数。也等价于原序列的最长上升子序列的长度。证明见《算法竞赛入门到进阶》第130页#include<bits/stdc++.h>using namespace std;const int N=2000;int h[N],f[N];int n;int LIS(){ int ans=1; int dp[N]; for(int i=1;i<=n;i++) { dp[i]=1; .

2022-03-16 15:03:05 158

原创 DP——最大上升子序列和

#include<bits/stdc++.h>using namespace std;const int N=1010;int m[N],dp[N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>m[i]; int ans=0; for(int i=1;i<=n;i++) { dp[i]=m[i]; .

2022-03-15 19:49:26 87

原创 DP（最长上升子序列）——友好城市

#include<bits/stdc++.h>using namespace std;const int N=6000;pair<int,int> m[N];int dp[N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>m[i].first>>m[i].second; sort(m+1,m+n+1); int.

2022-03-15 19:39:52 299

原创 DP（最长上升子序列）——登山

#include<bits/stdc++.h>using namespace std;const int N=1010;int m[N];int l[N],r[N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>m[i]; for(int i=1;i<=n;i++) { l[i]=1; .

2022-03-15 18:45:36 114

原创 DP（最长上升子序列）——怪盗基德的滑翔翼

#include<bits/stdc++.h>using namespace std;const int N=110;int w[N],dp[N];int main(){ int k; cin>>k; while(k--) { int n; cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; ..

2022-03-15 17:17:05 226

原创 DP——方格取数

#include<bits/stdc++.h>using namespace std;const int N=11;int m[N][N];int dp[2*N][N][N];int main(){ int n; cin>>n; int a,b,c; while(cin>>a>>b>>c && (a||b||c)) { m[a][b]=c; } ..

2022-03-14 20:27:29 215

原创 DP——摘花生

#include<bits/stdc++.h>using namespace std;const int N=110;int m[N][N];int dp[N][N];int main(){ int t; cin>>t; while(t--) { int h,l; cin>>h>>l; for(int i=1;i<=h;i++) for..

2022-03-14 17:24:33 325

原创 DP——数字三角形

#include<bits/stdc++.h>using namespace std;const int N=510;int t[N][N];int dp[N][N];int main(){ int n; cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>t[i][j]; for(int i=1;i&l.

2022-03-14 17:10:45 91

原创二维前缀和——激光炸弹

#include<bits/stdc++.h>using namespace std;const int maxn=5002;int s[maxn][maxn];int main(){ int n,r; cin>>n>>r; r=min(r,maxn-1); for(int i=0;i<n;i++) { int x,y,w; cin>>x>>y>&gt..

2022-03-12 21:58:29 446

原创快速幂+位运算——64位整数乘法

#include<bits/stdc++.h>using namespace std;long long slowMul(long long a,long long b,long long p){ long long ans=0; while(b) { if(b&1)ans=(ans+a)%p; a=a*2%p; b>>=1; } return ans;}int main().

2022-03-12 19:17:44 290

原创并查集+01背包——搭配购买

#include<bits/stdc++.h>using namespace std;const int maxn=10010;int s[maxn];int dp[maxn];int c[maxn],d[maxn];int find_set(int x){ if(s[x]!=x)s[x]=find_set(s[x]); return s[x];}void union_set(int x,int y){ x=find_set(x); y=fi.

2022-03-11 15:38:37 297

原创并查集——格子游戏

#include<bits/stdc++.h>using namespace std;const int maxn=40010;int s[maxn];int n,m;void init_set(){ for(int i=0;i<=maxn;i++) s[i]=i;}int get(int x,int y){ return x*n+y;}int find_set(int x){ if(s[x]!=x)s[x]=find_set(..

2022-03-11 14:20:48 5258

原创 PTA——银行排队问题之单窗口“夹塞”版（有详细注释）

一道队列题，但我还用的map，不知道不用map要怎么写这道题题目链接第一次自己写没考虑到窗口空闲的情况，看了题解才做出来的，这里附上参考题解的链接里面还有各测试点的数据数据结构与算法题目集7-48——银行排队问题之单窗口“夹塞”版#include<bits/stdc++.h>using namespace std;struct people{ string name; int arrive; int cost;};queue<people>

2020-11-18 17:03:29 1295

原创 HDU-Tunnel Warfare 使用set与stack的解法

HDU-Tunnel Warfare 使用set与stack的解法题目链接：Tunnel Warfare注意：此方法在1000ms限制的POJ中会超时题目：一般来说，通过隧道连接的村庄成一直线。除了两端的两个村庄外，每个村庄都与两个相邻的村庄直接相连。输入:输入的第一行包含两个正整数n和m（n，m≤50,000），表示村庄和事件的数量。接下来的m行中的每行都描述一个事件。D x：第x个村庄被摧毁。Q x：陆军司令部要求第x个村庄包括其自身直接或间接联系的村庄数。R：最后被摧毁的村庄被重建

2020-10-28 01:07:30 193

原创 C语言——归并排序

归并排序看着算法导论的伪代码写出来的因为书中数组下标从1开始，为了转换简便，我的代码的两个临时数组也从1开始//归并排序 #include<stdio.h>void MERGE(int A[],int a,int b,int r){ int i,j,k; int n1,n2; n1=b-a+1; n2=r-b; int L[n1],R[n2]; for(i=1;...

2020-02-03 20:07:54 376

空空如也

空空如也