几种算法简介（三）
1.加法(函数输出vector=A+B）T（n)=O(n+m)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <bits/stdc++.h> using namespace std; const int maxn=1e6+5; char s1[maxn],s2[maxn]; vector<int> add(vector<int> A,vector<int> B) { vector<int> result; int L1=A.size(); int L2=B.size(); int c=0,i=0; while(i<min(L1,L2)) { result.push_back((A[i]+B[i]+c)%10); c=(A[i]+B[i]+c)/10; i++; } while(i<L1) { result.push_back((A[i]+c)%10); c=(A[i]+c)/10; i++; } while(i<L2) { result.push_back((B[i]+c)%10); c=(B[i]+c)/10; i++; } if(c>0) result.push_back(c); return result; } |
2.减法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | vector<int> sub(vector<int> &A,vector<int> &B) { int flag=0; if(A<B) { flag=1; swap(A,B); } int t=0,i=0,L1=A.size(),L2=B.size(); while(i<L2) { if(A[i]-t>=B[i]) { result.push_back(A[i]-B[i]-t); t=0; } else { result.push_back(A[i]+10-B[i]-t); t=1; } i++; } while(i<L1) { if(A[i]-t>=0) { result.push_back(A[i]-t); t=0; } else { result.push_back(A[i]+10-t); t=1; } i++; } i=result.size()-1; while(result[i]==0) { result.pop_back(); i--; if(i<0) break; } if(result.size()==0) result.push_back(0); if(flag==1) result[i]*=-1; return result; } |
3.乘法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include <bits/stdc++.h> using namespace std; vector<int> multiply(vector<int> A,vector<int> B) { vector<int> C; int k=0,m=A.size(),n=B.size(); for(int i=0;i<m+n;i++) { C.push_back(0); for(int j=max(i+1-n,0);j<=i;j++) { if(j>=m) break; if(j<m&&i-j<n) C[i]+=A[j]*B[i-j]; } C[i]+=k; k=C[i]/10; C[i]%=10; } int u=C.size()-1; while(C[u]==0) { C.pop_back(); u--; if(u==0) break; } return C; } |
4.除法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <bits/stdc++.h> using namespace std; vector<int> Div(vector<int> A,int b,int& r) { vector<int> C; for(int i=A.size()-1;i>=0;i--) { r=r*10+A[i]; C.push_back(r/b); r%=b; } reverse(C.begin(),C.end()); while(C.size()>1&&C.back()==0) C.pop_back(); return C; } |
5.子矩阵的和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e6+5; ll S[1005][1005]={0}; int main() { int n,m,q; cin>>n>>m>>q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { ll c; scanf("%lld",&c); S[i][j]=c+S[i-1][j]+S[i][j-1]-S[i-1][j-1]; } for(int i=1;i<=q;i++) { int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; cout<<S[x2][y2]-S[x2][y1-1]-S[x1-1][y2]+S[x1-1][y1-1]<<endl; } return 0; } |
6.01背包，dp[i][j]的递推式只含dp[i-1][k]形式的滚动数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | #include <bits/stdc++.h> using namespace std; const int N=1005; int dp[N],w[N],v[N]; int main() { int n,V; cin>>n>>V; for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); for(int i=1;i<=n;i++) for(int j=V;j>=v[i];j--) dp[j]=max(dp[j],w[i]+dp[j-v[i]]); cout<<dp[V]<<endl; return 0; } |
7.完全背包
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #include <bits/stdc++.h> using namespace std; const int N=1005; int dp[N],w[N],v[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); for(int i=1;i<=n;i++) for(int j=v[i];j<=m;j++) dp[j]=max(dp[j],w[i]+dp[j-v[i]]); cout<<dp[m]<<endl; return 0; } |
8.多重背包问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <bits/stdc++.h> using namespace std; const int N=1005; int dp[N],w[N],v[N],s[N]; int main() { int n,m; cin>>n>>m; int cnt=0; for(int i=1;i<=n;i++) { int a,b,S,k=1; cin>>a>>b>>S; while(k<=S) { cnt++; w[cnt]=b*k; v[cnt]=a*k; S-=k; k*=2; } if(S>0) { cnt++; w[cnt]=b*S; v[cnt]=a*S; } } for(int i=1;i<=cnt;i++) for(int j=m;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); cout<<dp[m]<<endl; return 0; } |
9.分组背包
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <bits/stdc++.h> using namespace std; int w[105][105],v[105][105],dp[105],s[105]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>s[i]; for(int j=1;j<=s[i];j++) scanf("%d%d",&v[i][j],&w[i][j]); } for(int i=1;i<=n;i++) for(int j=m;j>=0;j--) for(int k=1;k<=s[i];k++) if(j>=v[i][k]) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]); cout<<dp[m]<<endl; return 0; } |
