klskr  #include<bits/stdc++.h> using namespace std; const int N=1e5; int c,n,m,p[N],ans; struct eg{ int a,b,w; bool operator <(const eg& egs){ return w<egs.w; } }e[N]; int find(int x){ if(p[x]!=x)p[x]=find(p[x]); return p[x]; } void klskr(){ for(int i=0;i<m;i++){ int x=find(e[i].a...

dijkstra  #include<bits/stdc++.h> using namespace std; const int N=1010; int n,m,s,t; int g[N][N],d[N]; bool st[N]; int dijkstra(){ memset(d,0x3f,sizeof d); d[s]=0; for(int i=0;i<n;i++){ int t=-1; for(int j=1;j<=n;j++){ if(!st[j]&&(t==-1||d[t]>d[j])) t=j; } st[t]=1; for(int j=...

klskr  #include<bits/stdc++.h> using namespace std; const int N=1e6+9; int n,m,p[N],ans; struct eg{ int a,b,w; bool operator <(const eg& egs){ return w<egs.w; } }e[N]; int find(int x){ if(p[x]!=x)p[x]=find(p[x]); return p[x]; } void klskr(){ for(int i=0;i<m;i++){ int x=find(e[i].a...

#include<iostream> #include<cstring> using namespace std; const int N=1010; int f1[N][N],f2[N][N],n,a[N],ans1=1e9,ans2; //f[i][j]表示为i到j区间合并最小值 int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } int m=n*2; for(int i=1;i<=m;i++)a[i]+=a[i-1]; memset(f1,0x...

#include<iostream> using namespace std; const int N=110; int a[N],f1[N],f2[N],n; int main(){ cin>>n; for(int i=0;i<n;i++)cin>>a[i]; for(int i=1;i<n;i++) for(int j=0;j<=i;j++) if(a[j]<a[i])f1[i]=max(f1[i],f1[j]+1); for(int i=n-2;i>=0;i--) for(int j=i+1;j<n;j++) if(...

拆成01背包  #include<iostream> using namespace std; const int M=2010; int v[M],w[M],n,T,f[M],vv,ww,x,p=0; int main(){ cin>>n>>T; for(int i=1;i<n+1;i++){ cin>>x>>ww>>vv; while(x--){ w[++p]=ww; v[p]=vv; } } for(int i=1;i<p+1;i++){ for(int j=T;j>=w[i];j--){ f[j]...

#include<iostream> using namespace std; const int M=30010; int p[M],w[M],n,N,f[M]; int main(){ cin>>N>>n; for(int i=1;i<n+1;i++)cin>>w[i]>>p[i]; for(int i=1;i<n+1;i++){ for(int j=N;j>=w[i];j--){ f[j]=max(f[j],f[j-w[i]]+w[i]*p[i]); } } cout<<f[N]; return 0...

#include<iostream> using namespace std; const int N=1010; int t[N],w[N],n,T,f[N]; int main(){ cin>>T>>n; for(int i=1;i<n+1;i++)cin>>t[i]>>w[i]; for(int i=1;i<n+1;i++){ for(int j=T;j>=t[i];j--){ f[j]=max(f[j],f[j-t[i]]+w[i]); } } cout<<f[T]; return 0; }

#include<iostream> using namespace std; const int N=20000; int v[N],n,V,f[N]; int main(){ cin>>V>>n; for(int i=1;i<n+1;i++)cin>>v[i]; for(int i=1;i<n+1;i++){ for(int j=V;j>=v[i];j--){ f[j]=max(f[j],f[j-v[i]]+v[i]); } } cout<<V-f[V]; return 0; }

#include<bits/stdc++.h> using namespace std; int n,m; unordered_map<string,string>f;//存父节点 string find(string x){//返回x祖宗 if(f[x]!=x)f[x]=find(f[x]); //将路径上的所有父节点的父节点变为祖宗(压缩) return f[x]; } int main(){ cin>>n>>m; string s; for(int i=0;i<n;i++){ cin>>s; f[s]=s;//初始化父节点...

#include<bits/stdc++.h> using namespace std; const int N=310; bool s[N][N]; int m,t[N][N]; int dx[]={0,0,0,-1,1},dy[]={0,1,-1,0,0}; struct stu{ int x,y,t; }home; int main(){ cin>>m; int sx,sy,st; while(m--){ cin>>sx>>sy>>st; for(int i=0;i<5;i++){ int ex=sx+dx[i],ey=s...

#include<bits/stdc++.h> using namespace std; const int N=20; int n,m,cnt;//n行m列别被坑了 找半天发现原来这里错了 void dfs(int a,int b){ int dx[]={1,1,2,2},dy[]={2,-2,1,-1}; if(a==m&&b==n){ cnt++; return; } for(int i=0;i<4;i++){ int x=a+dx[i],y=b+dy[i]; if(x>=1&&y>=1&&x<=m&am...

#include<bits/stdc++.h> using namespace std; const int N=10; bool s[N]; int n=8,p[N],cnt=0; void dfs(int u){ if(u==n){ for(int i=0;i<n;i++){ cout<<p[i]; if(i!=n-1)cout<<" "; } cout<<endl; return; } for(int i=1;i<=8;i++){ if(!s[i]){ p[u]=i; s[i]=1; dfs(u+1); p[u]=0,s[i]=...

#include<bits/stdc++.h> using namespace std; int n,m; const int N=1e6+9; int a[N],c[N]; struct dd{ int d,s,t; }p[N]; bool ck(int x){//x为订单顺序 memset(c,0,sizeof(c)); for(int i=1;i<=x;i++) c[p[i].s]+=p[i].d,c[p[i].t+1]-=p[i].d; for(int i=1;i<=n;i++){ c[i]+=c[i-1]; if(c[i]>a[i])return 0; ...