- C++
各类题目模板
-
Luftmensch_zcx
LV 7
@
2025-9-7 15:16:32
一 高精度
1.1 高精度加法
话不多说，上代码！
#include<bits/stdc++.h>
using namespace std;
int main() {
string num1_str, num2_str; // 存储输入的两个大数字符串
int num1_arr[1000] = {0}, num2_arr[1000] = {0}, result_arr[1001] = {0}; // 数组用于存储数字的每一位
int i, len1, len2, max_len; // 变量声明：循环计数器，两个数字的长度，最大长度
// 输入两个大数
cin >> num1_str >> num2_str;
// 获取两个数字的长度
len1 = num1_str.size();
len2 = num2_str.size();
// 确定两个数字中较长的长度
max_len = max(len1, len2);
// 将第一个数字字符串转换为整数数组（逆序存储：个位在索引0位置）
for (i = 0; i < len1; i++)
{
num1_arr[len1 - 1 - i] = num1_str[i] - '0'; // 字符转数字并逆序存储
}
// 将第二个数字字符串转换为整数数组（同样逆序存储）
for (i = 0; i < len2; i++)
{
num2_arr[len2 - 1 - i] = num2_str[i] - '0'; // 字符转数字并逆序存储
}
// 逐位相加并处理进位
for (i = 0; i < max_len; i++)
{
// 将两个数字的当前位相加（包括可能的进位）
result_arr[i] += num1_arr[i] + num2_arr[i];
// 如果当前位的结果大于等于10，需要进位
if (result_arr[i] >= 10)
{
// 将进位加到下一位
result_arr[i + 1] += result_arr[i] / 10;
// 保留当前位的个位数
result_arr[i] %= 10;
}
}
// 检查最高位是否有进位
if (result_arr[max_len] > 0) {
max_len++; // 如果有进位，结果长度增加1
}
// 输出结果（从最高位到最低位）
for (i = max_len - 1; i >= 0; i--) {
cout << result_arr[i]; // 逆序输出，恢复正常的数字顺序
}
return 0;
}
1.2 高精度减法
#include<bits/stdc++.h>
using namespace std;
// 比较两个大数（逆序存储）的大小，判断A是否大于等于B
bool compare(const vector<int>& A, const vector<int>& B) {
if (A.size() != B.size()) return A.size() > B.size(); // 位数不同时直接比较长度
for (int i = A.size() - 1; i >= 0; i--) { // 位数相同时，从最高位开始比较
if (A[i] != B[i]) return A[i] > B[i];
}
return true; // 两数相等
}
// 高精度减法函数（假设A >= B，且A和B均为逆序存储的非负整数）
vector<int> subtract(const vector<int>& A, const vector<int>& B) {
vector<int> C; // 存储结果的动态数组
int borrow = 0; // 借位标志，0表示无借位，1表示有借位
// 逐位相减
for (int i = 0; i < A.size(); i++) {
int current = A[i] - borrow; // 减去上一位的借位
if (i < B.size()) current -= B[i]; // 如果B还有位数，减去B的当前位
/*
* (current + 10) % 10 巧妙处理两种情况：
* 1. 若current >= 0，结果为current，无需额外处理
* 2. 若current < 0，结果为current + 10（借位后的值）
*/
C.push_back((current + 10) % 10);
borrow = (current < 0) ? 1 : 0; // 若当前位不足，设置借位标志
}
// 去除结果的前导零（保留至少一位，例如结果0）
while (C.size() > 1 && C.back() == 0) {
C.pop_back();
}
return C;
}
int main() {
string num1, num2;
cin >> num1 >> num2;
// 将字符串逆序存储为整数数组（个位在索引0位置）
vector<int> A, B;
for (int i = num1.size() - 1; i >= 0; i--) A.push_back(num1[i] - '0');
for (int i = num2.size() - 1; i >= 0; i--) B.push_back(num2[i] - '0');
// 处理并输出结果
if (compare(A, B)) { // A >= B时，直接计算A - B
vector<int> result = subtract(A, B);
for (int i = result.size() - 1; i >= 0; i--) cout << result[i];
} else { // A < B时，计算B - A并输出负号
vector<int> result = subtract(B, A);
cout << '-';
for (int i = result.size() - 1; i >= 0; i--) cout << result[i];
}
return 0;
}
1.3高精度乘法
#include<bits/stdc++.h>
using namespace std;
string multiply(string num1, string num2) {
// 处理特殊情况：如果任一数为0，乘积直接为0
if (num1 == "0" || num2 == "0") {
return "0";
}
int n1 = num1.size();
int n2 = num2.size();
// 结果的最大可能长度为 n1 + n2
vector<int> result(n1 + n2, 0);
// 将两个数字逆序存储（个位在索引0位置）
vector<int> a(n1), b(n2);
for (int i = 0; i < n1; i++) {
a[i] = num1[n1 - 1 - i] - '0'; // 字符转数字并逆序存储
}
for (int i = 0; i < n2; i++) {
b[i] = num2[n2 - 1 - i] - '0'; // 字符转数字并逆序存储
}
// 模拟手工乘法：逐位相乘并累加
for (int i = 0; i < n2; i++) { // 遍历第二个数的每一位
for (int j = 0; j < n1; j++) { // 遍历第一个数的每一位
// 当前位的乘积应放在结果的 i+j 位置
// 这里先累加到结果数组，后续统一处理进位
result[i + j] += a[j] * b[i];
}
}
// 统一处理所有进位
for (int i = 0; i < n1 + n2 - 1; i++) {
result[i + 1] += result[i] / 10; // 进位加到高位
result[i] %= 10; // 当前位只保留个位数
}
// 转换为字符串并去除前导零
string resultStr;
for (int i = result.size() - 1; i >= 0; i--) {
// 跳过最高位可能存在的零（但保留最后一位即使是零）
if (i == result.size() - 1 && result[i] == 0) {
continue;
}
resultStr += to_string(result[i]);
}
return resultStr;
}
int main() {
string num1, num2;
cin >> num1 >> num2;
string product = multiply(num1, num2);
cout << product << endl;
return 0;
}
高精度除法不常考，并且较难，不易理解
二 搜索算法
提示，本章所用的两个算法大多数出现在图中，故而均已图为示例
2.1 深度搜索（dfs）
顾名思义，深度优先先对当前节点找下一个节点，直至到头；到头后回溯到前一个节点再次进行深度搜索
代码：
#include<bits/stdc++.h>
using namespace std;
void dfsRecursive(const vector<vector<int>>& graph, int node, vector<bool>& visited) {
visited[node] = true; // 标记当前节点已访问
cout << node << " "; // 处理节点（如打印）
for (int neighbor : graph[node]) { // 遍历所有邻居
if (!visited[neighbor]) { // 如果邻居未访问
dfsRecursive(graph, neighbor, visited); // 递归访问
}
}
}
void dfsIterative(const vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false); // 访问标记数组
stack<int> stk; // 显式栈
stk.push(start); // 起点入栈
while (!stk.empty()) {
int node = stk.top();
stk.pop();
if (!visited[node]) {
visited[node] = true; // 标记已访问
cout << node << " "; // 处理节点
// 将未访问邻居逆序入栈（保证顺序性）
for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
if (!visited[*it]) {
stk.push(*it);
}
}
}
}
}
int main() {
// 图的邻接表表示（无向图示例）
vector<vector<int>> graph = {
{1, 2}, // 节点0的邻居
{0, 3, 4}, // 节点1的邻居
{0, 5}, // 节点2的邻居
{1}, // 节点3的邻居
{1}, // 节点4的邻居
{2} // 节点5的邻居
};
vector<bool> visited_recursive(graph.size(), false);
dfsRecursive(graph, 0, visited_recursive);
cout << endl;
return 0;
}
2.2 广度优先bfs
不同于dfs，bfs优先查找当前节点的相邻节点，为了保证搜索顺序，使用队列来记录待查找的节点
代码：
#include<bits/stdc++.h>
using namespace std;
// 广度优先搜索函数
void bfs(int start, const vector<vector<int>>& graph) {
int n = graph.size(); // 图中节点数量
vector<bool> visited(n, false); // 记录节点是否被访问过
queue<int> q; // 辅助队列，用于BFS
// 从起始节点开始
visited[start] = true;
q.push(start);
while (!q.empty()) {
int current = q.front(); // 取出队列首部的节点
q.pop();
cout << current << " "; // 处理当前节点（这里简单打印）
// 遍历当前节点的所有邻居节点
for (int neighbor : graph[current]) {
// 如果邻居节点未被访问，标记并加入队列
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
// 图的邻接表表示示例
// 这里以一个有6个节点的图为例
vector<vector<int>> graph = {
{1, 2}, // 节点0的邻居是节点1和2
{0, 3, 4}, // 节点1的邻居是节点0、3、4
{0, 4, 5}, // 节点2的邻居是节点0、4、5
{1}, // 节点3的邻居是节点1
{1, 2}, // 节点4的邻居是节点1和2
{2} // 节点5的邻居是节点2
};
bfs(0, graph); // 从节点0开始进行BFS遍历
cout << endl;
return 0;
}
三 最短路径算法
1 条评论
-
TOOTD 有事没事别打扰我 SU @ 2025-10-13 4:37:16CSP -j 复赛模板复习
一、 排序
1 快速排序
#include<bits/stdc++.h> using namespace std; int n,a[100001]; void qsort(int l,int r){ int mid=a[(l+r)/2]; int i=l,j=r; while(i<=j){ while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j){ swap(a[i],a[j]); i++;j--; } } if(l<j) qsort(l,j); if(i<r) qsort(i,r); } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; qsort(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" "; return 0; }2 归并排序
#include<bits/stdc++.h> using namespace std; const int maxn=100001; int n,a[maxn],tmp[maxn]; void msort(int l,int r){ if(l>=r) return; int mid=l+r>>1; msort(l,mid);msort(mid+1,r); int k=0,i=l,j=mid+1; while(i<=mid&&j<=r){ if(a[i]<a[j]) tmp[k++]=a[i++]; else tmp[k++]=a[j++]; } while(i<=mid) tmp[k++]=a[i++]; while(j<=r) tmp[k++]=a[j++]; for(int k=0,i=l;i<=r;i++,k++) a[i]=tmp[k]; } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; msort(1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" "; return 0; }二、二分模板
#include<bits/stdc++.h> using namespace std; int n,k,a[101]; int erfen(int x,int y,int val){ int l=x,r=y,mid; while(l<r){ mid=(l+r)/2; if(a[mid]<val) l=mid+1; else r=mid; } return l; } int main(){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; cout<<erfen(1,n,k); return 0; } 或 #include<bits/stdc++.h> using namespace std; int n,k,a[101]; int erfen(int x,int y,int val){ int l=x,r=y,mid; while(l<r){ mid=(l+r+1)/2; if(a[mid]<val) l=mid; else r=mid-1; } return l; } int main(){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; cout<<erfen(1,n,k); return 0; }三、前缀和与差分
1 一 维前缀和
cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; }2 二维前缀和
//S[i, j] = 第i行j列格子左上部分所有元素的和 cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cin>>a[i][j]; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; } } //以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：? cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) cin>>a[i][j]; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]; } } cin>>x1>>y1>>x2>>y2; ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; cout<<ans;3 一维差分
int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]-a[i-1]; }4 二维差分
//给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：四、位运算
求n的第k位数字: n >> k & 1 返回n的最后一位1：lowbit(n) = n & -n五、离散化
六、单调栈 单调队列
//常见模型：找出滑动窗口中的最大值/最小值 int stk[N], tt,n; ...常见模型：找出滑动窗口中的最大值/最小值 #include<bits/stdc++.h> using namespace std; int n,k,a[1000001]; int ans=1,l=1,r=1; struct node{ int v,id; }q[1000001]; int main(){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ while(l<r&&q[r-1].v>=a[i]) r--; q[r].v=a[i];q[r].id=i;r++; if(l<r&&i-q[l].id>=k) l++; if(i>=k) cout<<q[l].v<<" "; } return 0; }七、树与图
1 邻接矩阵
g[a][b]//存储边a→b2 邻接表
int h[N], e[N], ne[N], idx;//双向边*2 //h头节点，e编号，ne下一节点下标 void add(int a, int b) {//连接a,b e[++idx] = b, ne[idx] = h[a], h[a] = idx;//采用头插法 }3 DFS
int h[N], e[N], idx, ne[N]; bool st[N];// 需要标记数组st[N] void dfs(int u) { st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { dfs(j); } } }4 BFS
int h[N], e[N], idx, ne[N]; bool st[N]; // int q[N];//模拟队列 queue<int>q; int bfs() { // int hh=0,tt=0;//头节点 尾节点 while(q.size())//当我们的队列不为空时 { int t=q.front();//取出队列头部节点 for(int i=h[t];i;i=ne[i])//遍历t节点的每一个邻边 { int j=e[i]; if(!st[j]) { q.push(j);//把j结点 压入队列 } } } }5 dijkstra/堆优化
#include<bits/stdc++.h> using namespace std; const int maxn=200001; int n,m,s; int vis[100001],dis[100001]; int to[maxn],head[maxn],ne[maxn],w[maxn],idx; struct node{ int ds,pos; bool friend operator<(const node &a,const node &b){ return a.ds>b.ds; } }; priority_queue<node> q; void add(int x,int y,int z){ to[++idx]=y; w[idx]=z; ne[idx]=head[x]; head[x]=idx; } void dij(int x){ dis[x]=0;q.push({dis[x],x}); while(!q.empty()){ int cnt=q.top().pos;q.pop(); if(vis[cnt]) continue; vis[cnt]=1; for(int i=head[cnt];i;i=ne[i]){ int now=to[i]; if(dis[cnt]+w[i]<dis[now]){ dis[now]=dis[cnt]+w[i]; q.push({dis[now],now}); } } } } int main(){ ios::sync_with_stdio(0); cin>>n>>m>>s; for(int i=1;i<=m;i++){ int x,y,z;cin>>x>>y>>z; add(x,y,z); } for(int i=1;i<=n;i++) dis[i]=1e9; dij(s); for(int i=1;i<=n;i++) cout<<dis[i]<<" "; return 0; }6 SPFA
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=210001; int n,m,s; int vis[100001],dis[100001]; int to[maxn],head[maxn],ne[maxn],w[maxn],idx; queue<int> q; void add(int x,int y,int z){ to[++idx]=y; w[idx]=z; ne[idx]=head[x]; head[x]=idx; } void dij(int x){ dis[x]=0;q.push(x);vis[x]=1; while(!q.empty()){ int cnt=q.front();q.pop(); vis[cnt]=0; for(int i=head[cnt];i;i=ne[i]){ int now=to[i]; if(dis[cnt]+w[i]<dis[now]){ dis[now]=dis[cnt]+w[i]; if(!vis[now]){ q.push(now); vis[now]=1; } } } } } signed main(){ ios::sync_with_stdio(0); cin>>n>>m>>s; for(int i=1;i<=m;i++){ int x,y,z;cin>>x>>y>>z; add(x,y,z); } for(int i=1;i<=n;i++) dis[i]=(1<<31)-1; dij(s); for(int i=1;i<=n;i++) cout<<dis[i]<<" "; return 0; }7 kruscal
#include<bits/stdc++.h> using namespace std; int n,m,q,fa[5001],ans; struct node{ int x,y,z; bool friend operator<(const node &a,const node &b){ return a.z<b.z; } }ver[200001]; int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } int main(){ ios_base::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; ver[i].x=a; ver[i].y=b; ver[i].z=c; } sort(ver+1,ver+m+1); int cnt=0; for(int i=1;i<=m;i++){ int a=ver[i].x; int b=ver[i].y; if(find(a)==find(b)) continue; ans+=ver[i].z; fa[find(a)]=find(b); cnt++; if(cnt==n-1) break; } if(cnt<n-1) cout<<"orz"; else cout<<ans; return 0; }8 并查集
#include<bits/stdc++.h> using namespace std; int n,m,q,fa[1000001]; int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } int main(){ ios_base::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++){ int a,b; cin>>a>>b; fa[find(a)]=find(b); } cin>>q; for(int i=1;i<=q;i++){ int a,b; cin>>a>>b; a=find(a); b=find(b); if(a==b) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }八 数学
1 线性筛素数
int primes[N],cnt; bool st[N]; void get_primes(int n) { for(int i=2;i<=n;i++)//从2至n遍历 { if(!st[i])primes[cnt++]=i;//存储素数 for(int j=0;primes[j]<=n/i;j++)//primes[j]*i<=n { st[primes[j]*i]=true;//primes[j]是primes[j]*i的最小质因数 if(i%primes[j]==0)break;// prime[]数组中的素数是递增的,当i能整除prime[j]，那么i*prime[j+1]这个合数 肯定被prime[j]乘以某个数筛掉。 } } return; }2 试除求约数
for (int i = 1; i <= x / i; i ++ ) if (x % i == 0) { res.push_back(i); if (i != x / i) res.push_back(x / i);//x!=i*i }3 快速幂
#include<bits/stdc++.h> using namespace std; #define int long long int a,b,p; int fast(int n){ if(n==0) return 1; int t; t=fast(n/2); t=(t*t)%p; if(n%2==1) t=(t*a)%p; return t; } signed main(){ cin>>a>>b>>p; cout<<fast(b); return 0; }九 DP
1 序列DP——最长上升/下降子序列
//最长上升 #include<bits/stdc++.h> using namespace std; int n,a[5001]; int dp[5001],ans; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) dp[i]=1; for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); } } for(int i=1;i<=n;i++){ ans=max(dp[i],ans); } cout<<ans; return 0; } //最长下降 #include<bits/stdc++.h> using namespace std; int n,a[5001]; int dp[5001],ans; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) dp[i]=1; for(int i=1;i<=n;i++){ for(int j=1;j<i;j++){ if(a[i]<a[j]) dp[i]=max(dp[i],dp[j]+1); } } for(int i=1;i<=n;i++){ ans=max(dp[i],ans); } cout<<ans; return 0; }2背包问题
//1. 01背包 #include<bits/stdc++.h> using namespace std; int n,m,dp[1001]; int v[1001],w[1001],ans; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=m;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } for(int i=1;i<=m;i++){ if(dp[i]>ans) ans=dp[i]; } cout<<ans; return 0; } //2.完全背包 #include<bits/stdc++.h> using namespace std; int n,m,dp[1001]; int v[1001],w[1001],ans; int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>v[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=v[i];j<=m;j++){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } for(int i=1;i<=m;i++){ if(dp[i]>ans) ans=dp[i]; } cout<<ans; return 0; } //3.多重背包 #include<bits/stdc++.h> using namespace std; int n,m,dp[20001],cnt=0; int v[20001],w[20001],ans; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ int x,y,z;cin>>x>>y>>z; int t=1; while(z>=t){ z-=t; v[++cnt]=x*t; w[cnt]=y*t; t*=2; } if(z>0){ v[++cnt]=x*z; w[cnt]=y*z; } } 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]); } } for(int i=1;i<=m;i++){ if(dp[i]>ans) ans=dp[i]; } cout<<ans; return 0; } //4.混合背包 #include<bits/stdc++.h> using namespace std; int n,m,dp[20001],cnt=0; int v[20001],w[20001],ans,c[20001]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ int x,y,z;cin>>x>>y>>z; if(z>0){ int t=1; while(z>=t){ z-=t; v[++cnt]=x*t; w[cnt]=y*t; t*=2; c[cnt]=-1; } if(z>0){ v[++cnt]=x*z; w[cnt]=y*z; c[cnt]=-1; } } else if(z==0){ v[++cnt]=x; w[cnt]=y; c[cnt]=0; } else{ v[++cnt]=x; w[cnt]=y; c[cnt]=-1; } } for(int i=1;i<=cnt;i++){ if(c[i]==-1){ for(int j=m;j>=v[i];j--){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } else{ for(int j=v[i];j<=m;j++){ dp[j]=max(dp[j],dp[j-v[i]]+w[i]); } } } for(int i=1;i<=m;i++){ if(dp[i]>ans) ans=dp[i]; } cout<<ans; return 0; } //5.分组背包 #include<bits/stdc++.h> using namespace std; int n,m,a[101],dp[101]; struct node{ int v,w; }b[101][101]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; for(int j=1;j<=a[i];j++) cin>>b[i][j].v>>b[i][j].w; } for(int i=1;i<=n;i++){ for(int j=m;j>=0;j--){ for(int k=1;k<=a[i];k++){ if(j>=b[i][k].v) dp[j]=max(dp[j],dp[j-b[i][k].v]+b[i][k].w); } } } cout<<f[m]; return 0; } //6.二位费用背包 #include<bits/stdc++.h> using namespace std; int n,x,c,ans; int v[1001],m[1001],w[1001],f[101][101]; int main(){ cin>>n>>x>>c; for(int i=1;i<=n;i++) cin>>v[i]>>m[i]>>w[i]; for(int i=1;i<=n;i++){ for(int j=x;j>=v[i];j--){ for(int k=c;k>=m[i];k--){ f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]); } } } for(int i=1;i<=100;i++){ for(int j=1;j<=100;j++){ ans=max(ans,f[i][j]); } } cout<<ans; return 0; } //7.金明的预算方案（有限制的背包）3 区间DP
//合并问题 for(int len=2;len<=n;len++) for(int i=1;i<=n-len+1;i++) { int j=i+len-1; for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]- s[i-1]); }十 STL
vector, 变长数组，倍增的思想 size() 返回元素个数 empty() 返回是否为空 clear() 清空 front()/back() push_back()/pop_back() begin()/end() [] 支持比较运算，按字典序 pair<int, int> first, 第一个元素 second, 第二个元素 支持比较运算，以first为第一关键字，以second为第二关键字（字典序） string，字符串 size()/length() 返回字符串长度 empty() clear() substr(起始下标，(子串长度)) 返回子串 c_str() 返回字符串所在字符数组的起始地址 queue, 队列 size() empty() push() 向队尾插入一个元素 front() 返回队头元素 back() 返回队尾元素 pop() 弹出队头元素 priority_queue, 优先队列，默认是大根堆 size() empty() push() 插入一个元素 top() 返回堆顶元素 pop() 弹出堆顶元素 定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q; stack, 栈 size() empty() push() 向栈顶插入一个元素 top() 返回栈顶元素 pop() 弹出栈顶元素 deque, 双端队列 size() empty() clear() front()/back() push_back()/pop_back() push_front()/pop_front() begin()/end() [] set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列 size() empty() clear() begin()/end() ++, -- 返回前驱和后继，时间复杂度 O(logn) set/multiset insert() 插入一个数 find() 查找一个数 count() 返回某一个数的个数 erase() (1) 输入是一个数x，删除所有x O(k + logn) (2) 输入一个迭代器，删除这个迭代器 lower_bound()/upper_bound() lower_bound(x) 返回大于等于x的最小的数的迭代器 upper_bound(x) 返回大于x的最小的数的迭代器 map/multimap insert() 插入的数是一个pair erase() 输入的参数是pair或者迭代器 find() [] 注意multimap不支持此操作。 时间复杂度是 O(logn) lower_bound()/upper_bound() unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表 和上面类似，增删改查的时间复杂度是 O(1) 不支持 lower_bound()/upper_bound()， 迭代器的++，-- bitset, 圧位 bitset<10000> s; ~, &, |, ^ >>, << ==, != [] count() 返回有多少个1 any() 判断是否至少有一个1 none() 判断是否全为0 set() 把所有位置成1 set(k, v) 将第k位变成v reset() 把所有位变成0 flip() 等价于~ flip(k) 把第k位取反
- 1