函数模板大全总结（TBC FOREVER

〇、前言

并不是所有的都是我写的，有部分是收集的。若有侵权请联系我删除。

码风不喜勿喷...

可以按下ctrl+f进行查找，链接建议用中键点击。

建议开启O2,O3,C++14,std-namespace,<bits/stdc++.h>。

有时建议开long long int,<window.h>。

• O2,O3：pragma GCC optimize(2,3,"Ofast)；
• C++14：-std=c++14；
• std-namespace：using namespace std / std::；
• <bits/stdc++.h>：#include<bits/stdc++.h>；
• long long int：#define int long long & signed main()；
• <window.h>：#include<window.h>。

有的库函数比赛可能不能用...

一、 线性筛

//全局
int num[MAXN],len;
bool is[MAXN];
//

void Prime(int x){
	is[1]=1;
	for(int i=2;i<=x;i++){
		if(!is[i])	num[len++]=i;
		for(int j=0;j<len&&i*num[j]<x;j++){
			is[i*num[j]]=1;
			if(i%num[j]==0)	break;
		}
	}
}

//主函数内
int x;
Prime(x+1);
//在is中 0为质数
//

二、STL大全

STL文档下载 Click Here。

三、快读快写

1. 普通

   int rd(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
   void pt(int x){static int sta[35]={};int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top){putchar(sta[--top]+'0');}}
   
   //主函数内
   int n;
   n=rd();
   pt(n);
   //
   

2. __int128_t

   //全局
   #define int __int128
   //
   
   void rd128(int *p){char s[38]={};scanf("%s",s);int size=strlen(s);*p=0;for(int i=0;i<size;i++)if('0'<=s[i]&&s[i]<='9')*p=(*p)*10+s[i]-'0';}
   void pt128(int k){char s[38]={};int size=0;while(k)s[size++]=k%10+'0',k/=10;for(int i=0;i<size/2;i++)s[i]^=s[size-1-i]^=s[i]^=s[size-1-i];printf("%s",s);}
   
   //主函数内
   int n;
   rd128(&n);
   pt128(n);
   //注意 当n==0时 输出要特判!
   if(n==0)	puts("0");
   else pt128(n);
   //
   

四、论C++

Click Here。

五、判断回文数（串）

bool revstr(int p){
	string x=to_string(p),y;
	y=x;
	reverse(y.begin(),y.end());
	if(x==y)	return 1;
	return 0;
}

//主函数内
int x;
revstr(x);
//

判断回文串的话直接改1,2两行为：

bool revstr(string x){
	string y;

六、判断质数简单版（枚举...

bool Primee(int x){
	if(x<2)	return 0;
	if(x==2)	return 1;
	for(int i=2;i=x/i;i++){
		if(x%i==0)	return 0;
	}
	return 1;
}

//主函数内
int x;
if(Primee(x)){
    //TO-DO...
}else{
    //TO-DO...
}
//

七、排序

时间复杂度比对：

库函数的排序是根据数组中的数字来优先选择最快的排序方式。

除了库函数、冒泡排序、归并排序、快速排序以外都有可能错...（平时都用的库函数...

基本上每个排序都可以cmp自定义排序规则。

1. <algorithm>库函数：

   stable_sort(a+1,a+n+1,cmp);//正序排序 cmp可以自定义排序规则
   stable_sort(a+1,a+n+1,greater<int>());//倒序排序
   stable_sort(a.begin(),a.end());//用在STL中
   sort(a+1,a+n+1,cmp);//stable_sort是稳定排序 sort不稳定
   qsort(a+1,a+n+1,cmp);//快排吧... 在<cstdlib>(C)或<stdlib.h>(C++)中
   

2. 选择排序

   不稳定。

   模拟过程：

   

   void ssort(int x,int* y){
   	for(int i=1;i<=x;i++){
   		for(int j=i+1;j<=x;j++){
   			if(y[j]<y[i])	swap(y[i],y[j]);
   		}
   	}
   }
   
   //主函数内
   int n,a[MAXN];
   ssort(n,a);
   //
   

3. 插入排序

   稳定的。

   模拟过程：

   

   void isort(int x,int* y){
   	for(int i=1,j,k;i<=x;i++){
   		j=i-1,k=y[i];
   		while(j&&y[j]>k)	y[j+1]=y[j--];
   		y[j+1]=k;
   	}
   }
   
   //主函数内
   int n,a[MAXN];
   isort(n,a);
   //
   

4. 桶排序

   见桶排序 - OI Wiki、计数排序 - OI Wiki。

5. 冒泡排序

   void bubsort(int x,int* y){
   	for(int i=1;i<n;i++){
   		for(int j=1;j<=n-i;j++){
   			if(a[j]>a[j+1])	swap(a[j],a[j+1]);
   			//or if(!cmp(a[j],a[j+1]))	swap(a[j],a[j+1]);
               //cmp可以自定义排序规则
   		}
   	}
   }
   
   //主函数内
   int n,a[MAXN];
   bubsort(n,a);
   //
   

   求逆序对？

   还是用归并排序吧...

6. 归并排序

   //全局
   int n,a[MAXN],t[MAXN];
   //t为临时所需变量
   //
   
   void msort(int l,int r){
   	if(l==r)	return;
   	int mid=(l+r)/2;
   	msort(l,mid);
   	msort(mid+1,r);
   	int p=l,q=mid+1,k=l;
   	while(p<=mid&&q<=r){
   		if(a[p]<=a[q])	t[k++]=a[p++];
   		else	t[k++]=a[q++];
   	}
   	while(p<=mid)	t[k++]=a[p++];
   	while(q<=r)	t[k++]=a[q++];
   	for(int i=l;i<=r;i++)	a[i]=t[i];
   	return;
   }
   
   //主函数内
   int n,a[MAXN];
   msort(1,n);
   //
   

   求逆序对？

   //全局
   int n,a[MAXN],t[MAXN],ans;
   //t为临时所需变量 ans为逆序对个数
   //
   
   void msort(int l,int r){
   	if(l==r)	return;
   	int mid=(l+r)/2;
   	msort(l,mid);
   	msort(mid+1,r);
   	int p=l,q=mid+1,k=l;
   	while(p<=mid&&q<=r){
   		if(a[p]<=a[q])	t[k++]=a[p++];
   		else	t[k++]=a[q++],ans+=mid-p+1;;
   	}
   	while(p<=mid)	t[k++]=a[p++];
   	while(q<=r)	t[k++]=a[q++];
   	for(int i=l;i<=r;i++)	a[i]=t[i];
   	return;
   }
   
   //主函数内
   msort(1,n);
   //
   

7. 快速排序

   //全局
   int n,a[MAXN];
   //
   
   void qsort(int l,int r){
   	if(l>=r)	return;
   	int p=l,q=r;
   	while(p<q){
   		while(p<q&&a[q]>=a[l])	q--;
   		while(p<q&&a[p]<=a[l])	p++;
   		if(p!=q)	swap(a[p],a[q]);
   	}
   	if(l!=p)	swap(a[l],a[p]);
   	qsort(l,p-1);
   	qsort(p+1,r);
   }
   
   //主函数内
   qsort(1,n);
   //
   

8. 其他

   见排序简介 - OI Wiki。

八、快速幂

//全局
typedef unsigned long long int ull;
//

ull fpow(ull a,ull b){
	if(b==0)	return 1;
	if(b==1)	return a;
	ull tmp=fpow(a,b/2);
	if(b%2==0)	return tmp*tmp;
	return tmp*tmp*2;
}

//主函数内
fpow(2ull,n);
//

或

//全局
#define int long long
//

int fp(int x,int y,int k){
	int ans=1%k;
	for(;y;y>>=1){
		if(y&1){
			ans=ans*x%k;
		}
		x=x*x%k;
	}
	return ans;
}

//主函数内
int a,b,p;
fp(a,b,p);
//p为MOD的数
//

九、64位整数乘法

//全局
#define int long long
//

int c64(int x,int y,int k){
	int ans=0;
	for(;y;y>>=1){
		if(y&1){
			ans=(ans+x)%k;
		}
		x=x*2%k;
	}
	return ans;
}

//主函数内
int a,b,p;
c64(a,b,p);
//p为MOD的数
//

十、十进制数转化成二进制1后的个数

__builtin_popcount(n);

十一、子集

//全局
int n,a[MAXN];
//
void subj(){
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				cout<<a[j]<<' ';
                //也可以拿vector存
			}
		}
		cout<<'\n';
	}
}

//主函数内
stable_sort(a,a+n);//从0开始存
subj();
//

十二、DP

1. 最长上升子序列

   

   int f(){
   	dp[1]=1;
   	int ans=1;
   	for(int i=2;i<=n;i++){
   		dp[i]=1;
   		for(int j=1;j<i;j++){
   			if(a[j]<a[i]){
   				dp[i]=max(dp[i],dp[j]+1);
   				ans=max(dp[i],ans);
   			}
   		}
   	}
   	return ans;
   }
   

2. 最长上升子序列（两条序列版

   题目描述

   给你一个二维整数数组envelopes，其中envelopes[i]=[wi,hi]，表示第个信封的宽度和高度。

   当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

   请计算，最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

   注意：不允许旋转信封。

   #include<bits/stdc++.h>//真懒！
   using namespace std;
   const int MAXN=1e4+5;
   int n,ans,dp[MAXN];
   struct msg{
   	int x,y;
   }a[MAXN];
   bool cmp(msg x,msg y){
   	return x.x==y.x?x.y<y.y:x.x<y.x;
   }
   bool pan(int x,int y){
   	return a[y].y<a[x].y&&a[y].x<a[x].x?1:0;
   } 
   signed main(){
   	cin>>n;
   	for(int i=1;i<=n;i++)	cin>>a[i].x>>a[i].y;
   	stable_sort(a+1,a+n+1,cmp);
   	for(int i=1;i<=n;i++){
   		dp[i]=1;
   		for(int j=1;j<i;j++){
   			if(pan(i,j)){
   				dp[i]=max(dp[i],dp[j]+1);
   		        ans=max(ans,dp[i]);
   			}
   		}
   	} 
   	cout<<(ans==0?1:ans);
   	return 0;
   }
   

3. 最长上升子序列（困难版

   题目描述

   给定一个序列，从中选取若干个数，使得这一组数组成的序列满足且，求这个序列的最长长度。

   输入格式

   第一行一个整数。

   接下来一行个整数表示序列。

   输出格式

   一行一个整数表示最长序列的长度。

   样例

   样例输入

   5
   1 5 1 2 4
   

   样例输出

   3
   

   数据范围与提示

   组成的数列为。

   对于的数据，。

   对于的数据，。

   int f(){
       int ans,Max;
   	memset(dp,127,sizeof dp);
   	ans=0,Max=dp[0];
   	for(int i=0;i<n;i++){
   		*lower_bound(dp,dp+n,a[i])=a[i];
   	}
   	while(dp[ans]!=Max)	ans++;
       return ans;
   }
   

4. 最长上升子序列（输出序列版

   题目描述

   给定一个整数序列。求它的一个递增子序列，使子序列的元素个数尽量多，元素不一定要求连续。

   输入格式

   第行：个整数()，表示序列中元素的个数.

   第~行：每行个整数()，第行表示序列中的第个元素。

   输出格式

   第行：个整数，表示最长上升子序列的长度。

   第行：个用单个空格分开的整数，表示找到了最长上升子序列。输出的是序列中的元素，并非下标。如果有多个长度等于的子序列，则输出最靠前的个。

   样例

   样例输入

   8
   1
   3
   2
   4
   3
   5
   4
   6
   

   样例输出

   5
   1 3 4 5 6
   

   #include<bits/stdc++.h>//懒得搞成函数咯...
   using namespace std;
   const int MAXN=5e4+5;
   int n,a[MAXN],dp[MAXN],pre[MAXN],t,b[MAXN];
   int rd(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
   void pt(int x){static int sta[35]={};int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top){putchar(sta[--top]+'0');}}
   int f(){
   	int ans=0;
   	dp[1]=1;
   	for(int i=2;i<=n;i++){
   		dp[i]=1;
   		for(int j=1;j<i;j++){
   			if(a[j]<a[i]&&dp[j]+1>dp[i]){
   				dp[i]=dp[j]+1;
   				b[i]=j;
   			}
   			if(dp[i]>ans)	ans=dp[i],t=i;
   		}
   	}
   	return ans;
   }
   signed main(){
   	n=rd();
   	for(int i=1;i<=n;i++)	a[i]=rd();
   	if(n==1){
   		cout<<1<<'\n'<<a[1];
   		return 0;
   	}
   	int tmp=f();
   	pt(tmp);
   	puts("");
   	while(t!=0){
   		pre[++pre[0]]=t;
   		t=b[t];
   	}
   	for(int i=pre[0];i>=1;i--)	cout<<a[pre[i]]<<' ';
   	return 0;
   } 
   

   也可写一个output函数来递归输出答案。

5. 最大连续子序列和

   给定一个有（）个整数的序列，要求求出其中最大连续子序列的和。

   例如:
   
   序列(-2,11,-4,13,-5,-2)的最大子序列和为20
   
   序列(-6,2,4,-7,5,3,2,-1,6,-9,10,-2)的最大子序列和为16。
   

   规定一个序列最大连续子序列和至少是，如果小于，其结果为。

   输入格式

   第一行输入一个整数。

   第二行输入个用空格分开的整数。

   输出格式

   输出一个整数，表示这个序列的最大连续子序列的和。

   样例

   样例输入1：

   6
   -2 11 -4 13 -5 -2
   

   样例输出1：

   20
   

   样例输入2：

   12
   -6 2 4 -7 5 3 2 -1 6 -9 10 -2
   

   样例输出2：

   16
   

   数据范围与提示

   。

   我竟然没用DP...

   #include<bits/stdc++.h>//懒得搞成函数咯...
   using namespace std;
   const int MAXN=1e2+5;
   int n,ans,t,sum;
   int rd(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
   void pt(int x){static int sta[35]={};int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top){putchar(sta[--top]+'0');}}
   signed main(){
   	n=rd();
   	for(int i=1;i<=n;i++)	t=rd(),sum=max(sum+t,t),ans=max(ans,sum);
   	pt(ans);
   	return 0;
   } 
   

6. 最长公共子序列

   

   数据范围与提示

   最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。字符串长度小于等于。

   //全局
   int n,m,dp[MAXN][MAXN]; 
   string a,b,ans;
   //
   
   int f(){
   	int ans=0;
   	for(int i=1;i<=n;i++){
   		for(int j=1;j<=m;j++){
   			if(a[i-1]==b[j-1])	dp[i][j]=dp[i-1][j-1]+1;
   			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
   			ans=max(dp[i][j],ans);
   		}
   	}
   	return ans;
   }
   
   //主函数内
   int ans=f();
   //
   

7. 最长公共子序列（输出序列版

   

   //全局
   int n,m,dp[MAXN][MAXN]; 
   string a,b,ans;
   //
   
   int f(){
   	for(int i=1;i<=n;i++){
   		for(int j=1;j<=m;j++){
   			if(a[i-1]==b[j-1])	dp[i][j]=dp[i-1][j-1]+1;
   			else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
   		}
   	}
   	return dp[n][m];
   }
   void print(int i,int j){
   	if(i==0||j==0)	return;
   	if(a[i-1]==b[j-1]){
   		ans+=a[i-1];
   		print(i-1,j-1);
   	}else{
   		if(dp[i][j-1]>dp[i-1][j])	print(i,j-1);
   		else	print(i-1,j);
   	}
   }
   
   //主函数内
   int ans=f();
   print(n,m);
   reverse(ans);
   //
   

8. 最长公共上升子序列（简单版

   不会...
   见困难版...
   

9. 最长公共上升子序列（困难版

   题目描述

   给出两个整数序列和，求它们的最长公共上升子序列。

   输入格式

   第行：个整数，表示第个整数序列的长度。

   第行：个整数。

   第行：个整数，表示第个整数序列的长度。

   第行：个整数。

   输出格式

   第行：个整数，表示最长公共上升子序列的长度。

   样例

   样例输入

   5
   1 4 2 5 -12
   4
   -12 1 2 4
   

   样例输出

   2
   

   int f(){
   	for(int i=1;i<=m;i++){
   		int x=1;
   		for(int j=1;j<=n;j++){
   			if(b[i]!=a[j])	dp[i][j]=dp[i-1][j];
   			if(b[i]==a[j])   dp[i][j]=x;
   			if(b[i]>a[j]){
                   if(x<=dp[i-1][j]+1)	x=dp[i-1][j]+1;
               }
               ans=max(ans,dp[i][j]);
   		}
   	}
   	return ans;
   }
   

10. 最长公共上升子序列（输出序列版

    题目描述

    研究发现，大猩猩的基因序列和人的基因序列只有的区别，更进一步，不仅仅离人最近的大猩猩和人的基因序列高度近似，就连以打洞为生的老鼠和人的基因序列也有高达的相同序列。于是有魔法师提出一个大胆设想，即改变人类的某些特定基因以期产生超级人类。

    现在，他们要做的第一步是将两种不同生物的基因序列转换成两个整数序列，并试图确定他们的最大公共上升子序列的长度，例如有序列为，序列为，其最长公共子序列是，而最长公共递增子序列应该是。

    输入格式

    输入每个序列由个整数组成()，个整数范围在()之间。

    输出格式

    第一行输出最长公共上升子序列长度，第二行输出该子序列，如果该序列有多个答案，输出任意序列的编号字典序最小的一个。

    样例

    样例输入

    5
    1 4 2 5 -12
    4
    -12 1 2 4
    

    样例输出

    2
    1 4
    

    数据范围与提示

    输出按第一个序列的数字的编号字典需最小的那一组最长公共子序列

    #pragma GCC optimize(2,3,"Ofast")//懒得搞成函数咯...
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=5e3+5;
    int n,m,dp[MAXN][MAXN],a[MAXN]={INT_MIN},b[MAXN]={INT_MIN},pre[MAXN],o;
    int f(){
    	int ans=0;
    	for(int i=1;i<=m;i++){
    		int x=1,y=0;
    		for(int j=1;j<=n;j++){
    			if(b[i]!=a[j])	dp[i][j]=dp[i-1][j];
    			if(b[i]==a[j])   dp[i][j]=x,pre[j]=y;
    			if(b[i]>a[j]){
                    if(x<=dp[i-1][j]+1)	x=dp[i-1][j]+1,y=j;
                }
                ans=max(ans,dp[i][j]);
    		}
    	}
    	return ans;
    }
    void print(int x){
    	if (x==pre[x])	return;
        if (!o)	return;
        o--;
        print(pre[x]);
        cout<<a[x]<<' ';
    }
    signed main(){
    	cin>>n;
    	for(int i=1;i<=n;i++)	cin>>a[i];
    	cin>>m;
    	for(int i=1;i<=m;i++)	cin>>b[i];
    	int ans=f();
    	cout<<ans<<'\n';
    	int t=0;
    	for(int i=1;i<=n;i++){
    		if(o<dp[m][i]){
    			o=dp[m][i];
    			t=i;
    		}
    	}
    	print(t);
    	return 0;
    } 
    

11. 最大子矩阵（困难版

    题目描述

    事实上，宇宙中可以看到的物质只占宇宙总质量的不到，剩下的多是看不见摸不着的暗物质。暗物质能量惊人，是星际航行中无穷无尽强大动力的来源，而魔法世界的魔法实际上也是利用了围绕在我们四周但我们却毫无察觉的暗物质能量。

    现在，为了阻击修罗王的机器人军团，魔法世界使用了暗物质能量炮，暗物质能量炮攻击范围是一个矩形，攻击后可以使该范围内的机器人全部失灵。已知机器人军团在一个二维的矩阵中，矩阵中的各元素数代表该处的机器人数量，请确定一个小的矩阵，使这个小矩阵中所有元素的和最大。

    输入格式

    第一行为两整数，，（）。

    以下行，每行列，为矩阵中各元素的值。

    输出格式

    一个整数，即最大子矩阵和。

    样例

    样例输入

    4 3
    1 -8 -8
    1 1 1
    -8 1 2
    -8 1 1
    

    样例输出

    7
    

    #include<bits/stdc++.h>//懒死了...
    #define int long long
    using namespace std;
    const int MAXN=2e2+5;
    int a[MAXN][MAXN],ans,b[MAXN][MAXN],n,m;
    int rd(){int x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}
    void pt(int x){static int sta[35]={};int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top){putchar(sta[--top]+'0');}}
    signed main(){
    	n=rd(),m=rd();
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			a[i][j]=rd();
    			b[i][j]=a[i][j]+b[i-1][j];
    		}
    	}
    	for(int i=0;i<=n;i++){
    		for(int j=i+1;j<=n;j++){
    			int c[10005]={};
    			for(int k=1;k<=m;k++){
    				c[k]=max(b[j][k]-b[i][k],c[k-1]+b[j][k]-b[i][k]);
    				ans=max(ans,c[k]);
    			}
    		}
    	}
    	cout<<ans;
    	return 0;
    }
    

12. 0/1背包问题

    题目描述

    有一个最多能装千克的背包，有块魔法石，它们的重量分别是，它们的价值分别是。若每种魔法石只有一件，问能装入的最大总价值。

    输入格式

    第一行为两个整数和，以下行中，每行两个整数，分别代表第件物品的重量和价值。

    输出格式

    输出一个整数，即最大价值。

    样例

    样例输入

    8 3
    2 3
    5 4
    5 5
    

    样例输出

    8
    

    数据范围与提示

    。

    int f(){
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<=m;j++){
    			if(j>=w[i])	dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
    			else	dp[i][j]=dp[i-1][j];
    		}
    	}
    	return dp[n][m];
    } 
    
    //主函数内
    cin>>w[i]>>c[i];
    //
    

13. 0/1背包问题（困难版

    题目描述

    张琪曼：“为什么背包一定要完全装满呢？尽可能多装不就行了吗？”

    李旭琳：“你说得对，这和墨老师曾告诉我们的‘日中则昃，月满则亏’是一个道理。”所以，现在的问题是，她们有一个背包容量为(正整数，)，同时有个魔法石()，每个魔法石有一个体积 (正整数)。要求从个魔法石中，任取若干个装入包内，使背包的剩余空间为最小。

    输入格式

    第一行为一个整数，表示背包容量，第二行为一个整数，表示有个魔法石，接下来行，分别表示这个魔法石的各自体积。

    输出格式

    只有一个整数，表示背包剩余空间。

    样例

    样例输入

    24     
    6      
    8      
    3
    12
    7
    9
    7
    

    样例输出

    0
    

    int f(){
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=w[i];j--){
    			dp[j]=max(dp[j],dp[j-w[i]]+w[i]);
    		}
    	}
    	return m-dp[m];
    } 
    
    //主函数内
    cin>>w[i];
    //
    

14. 0/1背包问题第k优解

    题目描述

    01背包的第个最大价值。注意，两种不同方法得到相同价值是算作同一个种。这意味着，可以得到的价值序列将是一个严格递减的序列，从第个最大值，第个最大值.....第个最大值。

    如果不同值的总数小于，就输出0。

    输入格式

    第一行包含一个整数,表示有几组测试数据。

    每一组测试数据分为三行：

    第一行包含三个整数()表示背包的数量，袋子的体积以及我们求的。

    第二行，包含个整数表示每个背包的价值。

    第三行，包含个整数表示每个背包的体积。

    输出格式

    每行一个整数，第大值 (答案小于)。

    样例

    样例输入

    3
    5 10 2
    1 2 3 4 5
    5 4 3 2 1
    5 10 12
    1 2 3 4 5
    5 4 3 2 1
    5 10 16
    1 2 3 4 5
    5 4 3 2 1
    

    样例输出

    12
    2
    0
    

    #pragma GCC optimize(2,3,"Ofast")//懒
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=1e3+5;
    int n,m,k,a[MAXN],b[MAXN],w[MAXN],c[MAXN],dp[MAXN][MAXN];
    int f(){
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=c[i];j--){
    			memset(a,0,sizeof a);
    			memset(b,0,sizeof b);
    			for(int o=1;o<=k;o++)	a[o]=dp[j-c[i]][o]+w[i],b[o]=dp[j][o];
    			int l,r,cnt;
    			l=r=cnt=1,a[k+1]=b[k+1]=-114514;
    			while(cnt<=k&&(a[l]!=-114514||b[r]!=-114514)){
    				if(a[l]>b[r])	dp[j][cnt]=a[l++];
    				else	dp[j][cnt]=b[r++];
    				if(dp[j][cnt]!=dp[j][cnt-1])	cnt++;
    			}
    		}
    	}
    	return dp[m][k];
    } 
    signed main(){
    	int t;
    	cin>>t;
    	while(t--){
    		memset(dp,0,sizeof dp);
    		memset(w,0,sizeof w);
    		memset(c,0,sizeof c);
    		memset(a,0,sizeof a);
    		memset(b,0,sizeof b);
    		cin>>n>>m>>k;
    		for(int i=1;i<=n;i++)	cin>>w[i];
    		for(int i=1;i<=n;i++)	cin>>c[i];
    		cout<<f()<<'\n';
    	}
    	return 0;
    } 
    

15. 完全背包问题

    题目描述

    话说张琪曼和李旭琳又发现了一处魔法石矿（运气怎么这么好？各种嫉妒羡慕恨啊），她们有一个最多能装公斤的背包，现在有种魔法石，每种的重量分别是，每种的价值分别为。若每种魔法石的个数足够多，求她们能获得的最大总价值。

    输入格式

    第一行为两个整数，即。

    以后每行为两个整数，表示每块魔法石的重量和价值。

    输出格式

    获得的最大总价值。

    样例

    样例输入

    5 5
    1 1
    2 2
    3 3
    4 4
    5 5
    

    样例输出

    5
    

    数据范围与提示

    。

    int f(){
    	for(int i=1;i<=n;i++){
    		for(int j=w[i];j<=m;j++){
    			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
    		}
    	}
    	return dp[m];
    }
    
    //主函数内
    cin>>w[i]>>c[i];
    //
    

16. 完全背包求具体方案

    

    数据范围与提示

    。

    //全局
    int m,n,w[MAXN],c[MAXN],a[MAXN],ans[MAXN],len;
    vector<int> dp[MAXN];
    //
    
    int f(){
    	for(int i=1;i<=n;i++){
    		for(int j=w[i];j<=m;j++){
    			if(ans[j-w[i]]+c[i]>ans[j]){
    				dp[j]=dp[j-w[i]],ans[j]=ans[j-w[i]]+c[i];
    				dp[j].push_back(i);
    			}
    		}
    	}
    	return ans[m];
    } 
    void paint(){
    	for(int i=0;i<dp[m].size();i++)	a[dp[m][i]]++,len=max(len,dp[m][i]);
    	for(int i=1;i<=len;i++){
    		if(a[i]!=0)	cout<<i<<' '<<a[i]<<'\n';
    	}
    }
    
    //主函数内
    cin>>c[i]>>w[i];
    //
    

17. 多重背包问题1

    

    int f(){
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			for(int l=0;l<=t[i]&&w[i]*l<=j;l++)	dp[i][j]=max(dp[i][j],dp[i-1][j-l*w[i]]+l*v[i]);
    		}
    	}
    	return dp[n][m];
    } 
    
    //主函数内
    cin>>w[i]>>v[i]>>t[i];
    //
    

18. 多重背包问题2（用二进制优化

    

    #pragma GCC optimize(2,3,"Ofast")
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=2e5+5;
    int n,m,len,w[MAXN],v[MAXN],dp[MAXN]; 
    int f(){
    	n=len;
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=w[i];j--){
    			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    		}
    	}
    	return dp[m];
    } 
    signed main(){
    	cin>>n>>m;
    	for(int i=1,x,y,z;i<=n;i++){
    		cin>>x>>y>>z;
    		for(int j=1;j<=z;j*=2)	z-=j,w[++len]=j*x,v[len]=j*y;
    		if(z>0)	w[++len]=z*x,v[len]=z*y;
    	}
    	cout<<f();
    	return 0;
    } 
    

19. 多重背包问题3（用单调队列优化

    

    见单调队列优化。

20. 混合背包

    

    #pragma GCC optimize(2,3,"Ofast")
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=1e4+5;
    int m,n,w[MAXN],v[MAXN],s[MAXN],dp[MAXN];
    signed main(){
    	cin>>m>>n;
    	for(int i=1;i<=m;i++)	cin>>w[i]>>v[i]>>s[i];
    	for(int i=1;i<=m;i++){
    		if(s[i]==-1){
    			for(int j=n;j>=w[i];j--)	dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    		}else if(s[i]==0){
    			for(int j=w[i];j<=n;j++)	dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    		}else{
    			for(int j=n;j>=w[i];j--){
    				for(int l=1;l<=min(j/w[i],s[i]);l++)	dp[j]=max(dp[j],dp[j-l*w[i]]+l*v[i]);
    			} 
    		}
    	}
    	cout<<dp[n];
    	return 0;
    } 
    

21. 二维费用背包

    

    #pragma GCC optimize(2,3,"Ofast")
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=1e4+5;
    int n,p,m,w[MAXN],v[MAXN],s[MAXN],dp[MAXN][MAXN];
    int F(){
    	for(int i=1;i<=n;i++){
    		for(int j=p;j>=v[i];j--){
    			for(int l=m;l>=s[i];l--){
    				dp[j][l]=max(dp[j][l],dp[j-v[i]][l-s[i]]+w[i]);
    			}
    		}
    	}
    	return dp[p][m];
    }
    signed main(){
    	cin>>n>>p>>m;
    	for(int i=1;i<=n;i++)	cin>>v[i]>>s[i]>>w[i];
    	cout<<F();
    	return 0;
    } 
    

22. 分组背包

    

    #pragma GCC optimize(2,3,"Ofast")
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=1e3+5;
    int n,p,m,w[MAXN][MAXN],v[MAXN][MAXN],cnt[MAXN],dp[MAXN];
    int F(){
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=0;j--){
    			for(int l=1;l<=cnt[i];l++){
    				if(j>=w[i][l])	dp[j]=max(dp[j],dp[j-w[i][l]]+v[i][l]);
    			}
    		}
    	}
    	return dp[m];
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>cnt[i];
    		for(int j=1;j<=cnt[i];j++)	cin>>w[i][j]>>v[i][j];
    	}
    	cout<<F();
    	return 0;
    } 
    

23. 有依赖的背包

    

    

    不会...见OI-Wiki。

24. 背包求方案数

    

    #pragma GCC optimize(2,3,"Ofast")
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=1e4+5;
    const int MOD=1e9+7;
    int n,m,w[MAXN],v[MAXN],t[MAXN],dp[MAXN]={1};
    int F(){
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=v[i];j--){
    			if(t[j]==t[j-v[i]]+w[i])	dp[j]+=dp[j-v[i]]%MOD;
    			else if(t[j]<t[j-v[i]]+w[i])	dp[j]=dp[j-v[i]]%MOD;
    			t[j]=max(t[j],t[j-v[i]]+w[i]);	
    		}
    	}
    	int Max,ans;
    	Max=ans=0;
    	for(int i=1;i<=m;i++)	Max=max(Max,t[i]);
    	for(int i=1;i<=m;i++){
    		if(t[i]==Max)	ans=(ans+dp[i])%MOD;
    	}
    	return ans;
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)	cin>>v[i]>>w[i];
    	cout<<F();
    	return 0;
    } 
    

25. 背包求具体方案

    

    #pragma GCC optimize(2,3,"Ofast")
    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int MAXN=1e5+5;
    int n,m,a[MAXN],b[MAXN],dp[MAXN];
    string ans[MAXN];
    string f(){
    	for(int i=1;i<=n;i++){
    		for(int j=m;j>=a[i];j--){
    			if(dp[j-a[i]]+b[i]>dp[j])	dp[j]=dp[j-a[i]]+b[i],ans[j]=ans[j-a[i]]+to_string(i)+' ';
    			else if(dp[j-a[i]]+b[i]==dp[j]){
    				string t=ans[j-a[i]]+to_string(i)+' ';
    				if(ans[j]>t)	ans[j]=t;
    			}
    		}
    	}
    	return ans[m];
    }
    signed main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)	cin>>a[i]>>b[i];
    	cout<<f();
    	return 0;
    } 
    

26. 区间DP-石子合并

    

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=2e2+5;
    int n,ans1=INT_MAX,ans2=INT_MIN,a[MAXN],sum[MAXN],dp1[MAXN][MAXN],dp2[MAXN][MAXN];
    signed main(){
    	memset(dp1,127,sizeof dp1);
    	memset(dp2,128,sizeof dp2);
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(i!=n) a[i+n]=a[i];
    	}
    	for(int i=1;i<=n*2-1;i++)	dp1[i][i]=dp2[i][i]=0,sum[i]=sum[i-1]+a[i];
    	for(int i=2;i<=n*2-1;i++){
    		for(int l=1,r;l<=n*2-1-i+1;l++){
    			r=l+i-1;
    			for(int k=l;k<=r;k++){
    				dp1[l][r]=min(dp1[l][r],dp1[l][k]+dp1[k+1][r]+sum[r]-sum[l-1]);
    				dp2[l][r]=max(dp2[l][r],dp2[l][k]+dp2[k+1][r]+sum[r]-sum[l-1]);
    			}
    		}
    	}
    	for(int i=n;i<=n*2-1;i++){
    		ans1=min(ans1,dp1[i-n+1][i]);
    		ans2=max(ans2,dp2[i-n+1][i]);
    	}
    	cout<<ans1<<'\n'<<ans2; 
    	return 0;
    }
    

    区间DP

    概述

    区间型动态规划，又称为合并类动态规划，是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的区间中哪些元素合并而来有很大的关系。

    思想

    区间 DP 实质上就是在一个区间上进行的动态规划，不仅要满足 DP 问题的最优子结构，还要符合在区间上操作的特点。

    其主要思想就是在小区间进行 DP 得到最优解，然后再利用小区间的最优解合并求大区间的最优解。

    往往会枚举区间，将区间分成左右两部分，再求出左右区间进行合并操作。这样一来，如果要得知一个大区间的情况，由于它必定是由从多个长度不一的小区间转移而来，那么可以通过求得多个小区间的情况，从而合并信息，得到大区间。

    即：已知区间长度为的所有状态，然后可以通过小于的状态转移到区间长度为的状态，一般是在外层循环遍历，内层循环遍历起点来解决。

    区间DP模板伪代码：

    for k : = 1 to n - 1 do      //区间长度
    	for i : = 1 to n - k do    //区间起点
    	    for j : = i to i + k - 1 do //区间中任意点
    			dp[i, i + k]: = max{dp[i, j] + dp[j + 1, i + k] + a[i, j] + a[j + 1, i + k]};
    

    区间长度必须要放到第一层循环，来保证方程中状态、值在之前就已计算出来

    其中可以灵活多变，其指的是合并区间时产生的附加值。