算法基础课第二部分

第四讲 数学知识

AcWing1381. 阶乘(同余，因式分解)

AcWing1381. 阶乘

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int main()
{int n;cin >> n;int res = 1, d2 = 0, d5 = 0;for (int i = 1; i <= n; i ++ ){int x = i;while (x % 2 == 0) x /= 2, d2 ++ ;//把2除干净---最终x=1 while (x % 5 == 0) x /= 5, d5 ++ ;//把5除干净---最终x=1 res = res * x % 10;//末位一定不是0}//2的个数一定比5的个数多 for (int i = 0; i < d2 - d5; i ++ ) res = res * 2 % 10;//上面的2还没来得及乘进去 cout << res << endl;return 0;
}

质数

AcWing 866. 质数的判定—试除法

AcWing 866. 试除法判定质数

#include<bits/stdc++.h>
using namespace std;
const int N=1E2+10;
bool is_prime(int x)//试除法---判断质数
{if(x<2)return false;for(int i=2;i<=x/i;i++)//这里最好写成这样{if(x%i==0)return false;}return true;
}
int main()
{int n;cin>>n;while(n--){int x;cin>>x;if(is_prime(x))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;} 

AcWing 868. 质数的判定—埃氏筛

埃氏筛：
筛法如何求质数捏，说起来很简单：首先，2是公认最小的质数，所以，先把所有2的倍数去掉；
然后剩下的那些大于2的数里面，最小的是3，所以3也是质数；
然后把所有3的倍数都去掉，剩下的那些大于3的数里面，
最小的是5，所以5也是质数……

上述过程不断重复，就可以把某个范围内的合数全都除去（就像被筛子筛掉一样），剩下的就是质数了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;int n;
bool st[N];//true:合数 false：质数   
int ans;
void is_prime()
{for(int i=2;i<=n;i++)//质数的定义从[2,+00} ---埃式筛{if(!st[i])//如果是质数 {	ans++;for(int j=i;j<=n;j+=i){st[j]=true; }}} 
}
int main()
{cin>>n;is_prime();cout<<ans<<endl;return 0;
}

AcWing867. 分解质因数—试除法

根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。n=p1^a1 * p2^a2 *p3^a3.....pn^an比如一个数16 在分解时先找到2这个质因子，然后由于16/2后还可以/2，所以会在2这个质因子上产生次方
不优化版本：从2~n 找到能整除的因子然后算次方这里有个性质：n中最多只含有一个大于sqrt(n)的因子。
证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕
于是我们发现最多只有一个大于sqrt(n)的因子，对其进行优化。
先考虑比sqrt(n)小的，代码和质数的判定类似最后如果n还是>1，说明这就是大于sqrt(n)的唯一质因子，输出即可。

#include<bits/stdc++.h>
using namespace std;
void divide(int x)
{for(int i=2;i<=x/i;i++){if(x%i==0)//当i是因数时---能保证一定是质数 {int cnt=0;//cnt记录每个质因数的指数while(x%i==0){x/=i;//将质数i除干净cnt++;}cout<<i<<" "<<cnt<<endl;//输出质因数i及其指数cnt}}if(x>1)cout<<x<<" "<<1<<endl;//输出大于sqrt(x)的那个质因数---10=2*5
}
int main()
{int n;cin>>n;while(n--){int x;cin>>x;divide(x);//分解质因数cout<<endl;}return 0;} 

AcWing 197. 阶乘—分解质因数—埃式筛

AcWing 197. 阶乘分解

下图题解–很清晰的思路

#include<bits/stdc++.h>
using namespace std;
const int N=1e6; int n;
bool st[N];//存储对应下标---是否是质数---埃式筛---false:质数
int cnt[N];//存储对应下标的质数---次方数
void prime()
{for(int i=2;i<=n;i++){if(!st[i])//是质数时 {for(int j=i+i;j<=n;j=j+i)st[j]=true; }}
}
int main()
{cin>>n;prime();for(int i=2;i<=n;i++)//---例如2(cnt[2]=1)*3(cnt[3]=1)*4(cnt[2]=1+2)*5(cnt[5]=1){if(!st[i])//是质数时 ---2、3、5{long long x=i;//质数i---例如i=2while(x<=n) //{cnt[i]+=n/x;//将质数i除干净    4/2=2 2/2=1  1/2=0---cnt[2]+2+1;x=x*i;   //2*2=4---4*2=8>5--结束循环}}} for(int i=2;i<=n;i++){if(!st[i])//如果是质数---输出质数+次方数{cout<<i<<" "<<cnt[i]<<endl;}}return 0;
}

约数

AcWing 869. 求约数—试除法

AcWing 869. 试除法求约数

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10;vector<int> get_divisors(int n)
{vector<int> vec;//存储所有的约数for(int i=1;i<=n/i;i++)//优化---不用遍历所有的i---同试除法---分解质因数{if(n%i==0){vec.push_back(i);if(n/i!=i)//特判一下---防止出现重复约数-- 避免 i==n/i, 重复放入---n是完全平方数vec.push_back(n/i); }}sort(vec.begin(),vec.end());//所有的约数从小到大排序return vec;
}
int n;
int main()
{cin>>n;while(n--){int x;cin>>x;auto vec=get_divisors(x);for(auto t:vec){cout<<t<<" ";}cout<<endl;}return 0;
}

AcWing 870. 约数个数—试除法—质因数

AcWing 870. 约数个数

约数个数定理
约数之和定理–证明+实例

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
typedef long long LL;
unordered_map<int,int> primes;//first：存储质数---second：存储质数的次方数
int main()
{int n;cin>>n;while(n--){int x;cin>>x;for(int i=2;i<=x/i;i++){while(x%i==0)//当i是一个质因子时---能保证一定是质数 {x=x/i;//将质因子除干净 primes[i]++;//质因子的指数++ }}if(x>1)	primes[x]++;//最后一个大于x/i的质因子 }LL ans=1;for(auto prime:primes)//约数之和定理{ans=ans*(prime.second+1)%MOD;}cout<<ans<<endl;return 0; } 

AcWing 871. 约数之和—上个题的题解

AcWing 871. 约数之和

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
typedef long long LL;
unordered_map<int,int> primes;//first：存储质数---second：存储质数的次方数
int main()
{int n;cin>>n;while(n--){int x;cin>>x;for(int i=2;i<=x/i;i++){while(x%i==0)//当i是一个质因子时---能保证一定是质数 {x=x/i;//将质因子除干净 primes[i]++;//质因子的指数++ }}if(x>1)	primes[x]++;//最后一个大于x/i的质因子 }LL ans=1;for(auto prime:primes){int p=prime.first;//底数int a=prime.second;//指数LL t=1;while(a--)//求解约数之和{t=(t*p+1)%MOD;}ans=ans*t%MOD; }cout<<ans<<endl;return 0;
}

AcWing 872. 最大公约数

AcWing 872. 最大公约数
建议直接调用c++STL中自带的__gcd()函数来求解最大公因数
（注意！函数前面有两个下划线哦。即：是“__gcd”而不是“_gcd”）

#include<iostream>
#include<bits/stdc++.h>
using namespace std;int main(){cout<<"输入两个数(求这俩数的最大公约数)：";int a,b; cin>>a>>b;cout<<"这两个数的最大公约数为："<<__gcd(a,b);}

最小公倍数

通过最大公约数来间接计算

#include<iostream>
using namespace std;
int gcd(int a,int b){if(b==0)return a;elsereturn gcd(b,a%b);
}
int main(){cout<<"输入两个数(求这俩数的最大公倍数)：";int a,b; cin>>a>>b;cout<<"这两个数的最大公倍数为："<<a*b/gcd(a,b);}

欧拉函数

AcWing874 线性筛法求欧拉函数

#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1000010;int primes[N];//存储筛出来的质数 
int cnt;//<=n的  质数的个数 
int phi[N];//phi[i]记录的是i的欧拉函数值  
bool st[N];//线性筛 状态数组存储是否被筛掉 false:质数  true：非质数 void get_eulers(int n)
{phi[1] = 1;for (int i = 2; i <= n; i++){if (!st[i])//此时 i是质数 {primes[cnt++] = i;//存储下这个质数 phi[i] = i - 1; //质数的欧拉函数值 = 质数值-1 }for (int j = 0; primes[j] <= n / i; j++){st[primes[j] * i] = false;//这个质数的倍数都标记非质数if (i % primes[j] == 0) {//如果primesj是i的最小质因子 //说明也是 i*primesj的最小质因子 //那么在计算phi i的过程中计算过了1-1/primesj这一项 //所以只要修正为primesj倍即可phi[i * primes[j]] = phi[i] * primes[j]; break;}phi[primes[j] * i] = phi[i] * (primes[j] - 1);//i % primes[j] != 0：primes[j]不是i的质因子，//只是primes[j] * i的最小质因子，//因此不仅需要将基数N修正为primes[j]倍，//还需要补上1 - 1 / primes[j]这一项，//因此最终结果phi[i] * (primes[j] - 1)}}
}int main()
{int n;cin >> n;get_eulers(n);LL res = 0;for (int i = 1; i <= n; i++) res += phi[i];printf("%lld\n", res);return 0;
}

快速幂

思路：
最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积

3^10=3*3*3*3*3*3*3*3*3*3//尽量想办法把指数变小来，这里的指数为103^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)3^10=(3*3)^53^10=9^5//此时指数由10缩减一半变成了5，而底数变成了原来的平方，求3^10原本需要执行10次循环操作，求9^5却只需要执行5次循环操作，
但是3^10却等于9^5,我们用一次（底数做平方操作）的操作减少了原本一半的循环量，特别是在幂特别大的时候效果非常好，
例如2^10000=4^5000,底数只是做了一个小小的平方操作，而指数就从10000变成了5000，减少了5000次的循环操作。//现在我们的问题是如何把指数5变成原来的一半，5是一个奇数，5的一半是2.5，但是我们知道，指数不能为小数，
因此我们不能这么简单粗暴的直接执行5/2，然而，这里还有另一种方法能表示9^59^5=（9^4）*（9^1）//此时我们抽出了一个底数的一次方，这里即为9^1，这个9^1我们先单独移出来,剩下的9^4又能够在执行“缩指数”操作了，把指数缩小一半，底数执行平方操作9^5=（81^2）*(9^1)//把指数缩小一半，底数执行平方操作9^5=（6561^1）*(9^1)//此时，我们发现指数又变成了一个奇数1，按照上面对指数为奇数的操作方法，应该抽出了一个底数的一次方，这里即为6561^1，这个6561^1我们先单独移出来，
但是此时指数却变成了0，也就意味着我们无法再进行“缩指数”操作了。9^5=（6561^0）*(9^1)*(6561^1)=1*(9^1)*(6561^1)=(9^1)*(6561^1)=9*6561=59049我们能够发现，最后的结果是9*6561，而9是怎么产生的？是不是当指数为奇数5时，此时底数为9。那6561又是怎么产生的呢？是不是当指数为奇数1时，此时的底数为6561。
所以我们能发现一个规律：最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

所以我们能发现一个规律：最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

#include<iostream>
#include<time.h>
using namespace std;
typedef long long ll;
ll ans;
ll base=0;
ll power=0;
ll fastPower(ll base,ll power){ans=1;while(power>0){if(power%2==0){//当幂指数为偶数时power=power/2;base=base*base%1000; 		}else//当幂指数为奇数时{power=power-1;//有没有这一步都一样，因为下一步中的除法为整除 ans=ans*base%1000;power=power/2;	base=base*base%1000;		}}return ans;
}
int main(){cin>>base>>power;clock_t start=clock();ans=fastPower(base,power);clock_t end=clock();cout << "the time cost is" << double(end - start) / CLOCKS_PER_SEC<<"s"<<endl;cout<<ans;
}

扩展欧几里得算法

中国剩余定理

高斯消元

求组合数

AcWing885. 求组合数 I (dp)

AcWing 885. 求组合数 I

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10,MOD=1e9+7;
int C[N][N];//C[i][j]---从i个中选取j个的种类数
void init()//初始化---组合数
{for(int i=0;i<N;i++){for(int j=0;j<=i;j++){if(j==0) C[i][j]=1;elseC[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;//从i个中选取j个的种类数=(不选第j个)+(选择第j个)}}
}
int n;
int main()
{init();cin>>n;while(n--){int a,b;cin>>a>>b;cout<<C[a][b]<<endl;}return 0;} 

201312-4csp有趣的数—组合数

AcWing 3195. 有趣的数

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,MOD=1e9+7;
typedef long long LL;
LL C[N][N];
LL ans=0;
void init()//初始化---组合数
{for(int i=0;i<N;i++){for(int j=0;j<=i;j++){if(j==0)C[i][j]=1;elseC[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;}}
}
int main()
{int n;cin>>n;init();for(int k=2;k<=n-2;k++)//选择01的总个数{ans=(ans+C[n-1][k] * (k-1) * (n-k-1)) % MOD;//注意取模的时机}cout<<ans<<endl; return 0;
}

容斥原理

博弈论

第五讲 动态规划

背包问题(有限制的选择问题)

01背包问题

AcWing2. 01背包问题-max

acwing2. 01背包问题

AcWing 2. 01背包问题（状态转移方程讲解）

从大到小

#include<bits/stdc++.h>using namespace std;const int N=1E3+10;int v[N];//体积 
int w[N];//价值 
int f[N][N];//dp数组 
int n;//物品数量 
int m;//背包容量 
int main()
{cin>>n>>m;for(int i=1;i<=n;i++)	cin>>v[i]>>w[i];//初始化for(int i=0;i<=n;i++)//从前i个物品中选，且总体积不超过0的集合---最大价值=0f[i][0]=0;for(int j=1;j<=m;j++)//从前0个物品中选，且总体积不超过j的集合---最大价值=0f[0][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i])//当背包容量能装下第i件物品时f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);} cout<<f[n][m]<<endl;return 0;} 

一维优化

01背包问题模板：for (int i = 1; i <= n; i ++)for (int j = 背包容量 ; j >=容量; j --)//注意了，这里的j是从大到小枚举，和完全背包不一样(相反)f[j] = max (f[j] , f[j - w[i]] + v[i]) ;

#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n, m;
int v[N], w[N];
int f[N];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 -- )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}

202209-2-csp- 何以包邮？min-》-max

AcWing 4700. 何以包邮？
70分写法

#include<bits/stdc++.h>
using namespace std;
const int N=33;
int n,x;
int w[N];//存储每本书的价格 
int res=1e8;
void dfs(int i,int sum)
{if(i==n)//如果到达第n件物品 {if(sum>=x)res=min(res,sum);}else{dfs(i+1,sum);//不选第i件物品时 dfs(i+1,sum+w[i]);//选第i件物品时 }
}
int main()
{cin>>n>>x;for(int i=0;i<n;i++)	cin>>w[i];dfs(0,0);cout<<res<<endl;return 0;
}

100分写法

#include<bits/stdc++.h>
using namespace std;
const int N=40,M=3e5+10;int w[N];//价值----存储每本书的价格  
int v[N];//容量 
int f[N][M];//从前i个物品中选，总体积不超过j的选法集合---
//属性：max int main()
{int n,x;cin>>n>>x;int sum=0;for(int i=1;i<=n;i++){cin>>w[i];v[i]=w[i];sum+=w[i];}int m=sum-x;f[0][0]=0;//初始化//状态计算 for(int i=1;i<=n;i++)//n件物品 for(int j=1;j<=m;j++)//总体积 {f[i][j]=f[i-1][j];if(j>=v[i])// 能装，需进行决策是否选择第i个物品f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}cout<<sum-f[n][m]<<endl;//总价值-背包装的最大值==即可包邮且花费最小 	return 0;} 

AcWing 3442. 神奇的口袋-计数

AcWing 3442. 神奇的口袋

这道题也是一道01背包问题
之前的f[i][j]:从前i个物品中选，且总体积不超过j的选法集合;
现在的f[i][j]:从前i个物品中选，体积正好等于j的选法的集合;属性变化---max--->计数这时候就与w[]无关了，那么在状态转移方程书写的时候:
表示不取第i个物品且体积正好等于j，f[i][j]=f[i - 1][j]
能够包含第i件物品时f[i][j]=f[i-1][j]+f[i-1][j-v[i]]因为表示的是不同的取法，一个包含第i个物品，一个不包含第i个物品f数组的初始化也和01背包问题不大相同
以前是体积不超过j，且选取的物品不超过i的最大价值，当i=0的时候表示什么都没选，自然最大价值就是0，
f[0][0]=0;现在是表示前i个物品选择之后，体积正好等于j的选法之和，f[i][0]表示什么都没选的时候，体积正好等于0，
f[i][0]=1;这是这种状态下唯一的一种选法但是f[0][1]....f[0][40]就表示什么都不选的情况下体积等于1-40的情况，没有一种选法会是这样，因此为0
f[0][j]=0;

#include<bits/stdc++.h>
using namespace std;
const int N=100;int v[N];
int f[N][N];//状态表示：从前i个物品中选，且总体积为j个选法集合
//属性：计数int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>v[i];//初始化for(int i=0;i<=n;i++)//从前i个物品中选，且总体积为0的选法集合有1种f[i][0]=1;for(int j=1;j<=40;j++)//表示什么都不选的情况下体积等于1-40的情况，没有一种选法会是这样，因此为0f[0][j]=0;//状态计算	for(int i=1;i<=n;i++)for(int j=1;j<=40;j++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=f[i-1][j]+f[i-1][j-v[i]];} cout<<f[n][40]<<endl;return 0;} 

一维优化

#include<bits/stdc++.h>
using namespace std;
const int N=20;int v[N];
int f[40];int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>v[i];f[0]=1;	for(int i=1;i<=n;i++)for(int j=40;j>=v[i];j--)f[j]=f[j]+f[j-v[i]];cout<<f[40]<<endl;return 0;
}

AcWing 8. 二维费用的背包问题—二维费用

AcWing 8. 二维费用的背包问题

#include<bits/stdc++.h>
using namespace std;
const int V=110,M=110;
const int N=1e3+10;
int v[N];
int m[N];
int w[N];int f[V][M];int main()
{int n,nv,nm;cin>>n>>nv>>nm;for(int i=1;i<=n;i++)cin>>v[i]>>m[i]>>w[i];//初始化f[0][0]=0;//状态计算for(int i=1;i<=n;i++)for(int j=nv;j>=v[i];j--)//01背包逆序for(int k=nm;k>=m[i];k--)//只要有一维体积是按从大到小循环就可以，另一维随意。f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);cout<<f[nv][nm]<<endl;return 0;
}

AcWing 3417. 砝码称重

AcWing 3417. 砝码称重

#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int B=1e5+10;//数组偏移量
const int M=2*B;//可以称出的重量int w[N];
bool f[N][M];//从前i个物品中选，可称出重量为j的所有方案的集合
//属性：boolint main()
{int n;cin>>n;int s=0;for(int i=1;i<=n;i++){cin>>w[i];s+=w[i];}f[0][0+B]=true;//什么砝码都没有时---可以凑出这种可能 for(int i=1;i<=n;i++)for(int j=-s;j<=s;j++){//不放置0---左为负，右为正 ---三个集合是或的关系---只要有一个非空---f[i][j]=truef[i][j+B]=f[i-1][j+B];//不选择第i个砝码时 if(j-w[i]>=-s)//将第i个砝码放到左边时f[i][j+B]=f[i][j+B]|f[i-1][j+B-w[i]];if(j+w[i]<=s)//将第i个砝码放到右边时 f[i][j+B]=f[i][j+B]|f[i-1][j+B+w[i]];}int ans=0;for(int j=-s;j<=s;j++)//枚举所有重量---从(-s,s),但能称出来的重量仅有一半if(f[n][j+B])ans++;cout<<(ans-1)/2<<endl;//我们认为0不能算称出来的重量----return 0;} 

完全背包问题

AcWing 3. 完全背包问题-max

AcWing 3. 完全背包问题

AcWing 3. 完全背包问题—状态转移方程
闫氏DP分析法

注意状态转移方程的区别

#include<bits/stdc++.h>using namespace std;const int N = 1005;
int v[N];    // 体积
int w[N];    // 价值 
int f[N][N];  // f[i][j], j体积下前i个物品的最大价值 int main() 
{int n, m;   cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];//初始化for(int i=0;i<=n;i++)f[i][0]=0;//从前i个物品中选，总体积<=0的选法的集合--属性-max(只能什么都不选---)=0for(int j=1;j<=m;j++)f[0][j]=0;//从前0个物品中选，总体积<=j的选法的集合--属性-max(只能什么都不选---)=0//状态计算for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){//  当前背包容量装不进第i个物品，则价值等于前i-1个物品//if(j < v[i]) f[i][j] = f[i - 1][j];// 能装，需进行决策是否选择第i个物品if(j>=v[i])   f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);}           cout << f[n][m] << endl;return 0;
}

一维写法

完全背包问题模板：for (int i = 1; i <= n; i ++)for (int j = 体积; j <= 背包容量; j ++)//注意了，这里的j是从小到大枚举，和01背包不一样f[j] = max (f[j] , f[j - w[i]] + v[i]) ;

#include<bits/stdc++.h>using namespace std;const int N = 1005;
int v[N];   
int w[N];    
int f[N];  int main() 
{int n, m;   cin >> n >> m;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];//初始化f[0]=0;//状态计算for(int i = 1; i <= n; i++) for(int j = v[i]; j <= m; j++) //注意j的初始值变化      f[j] = max(f[j], f[j - v[i]] + w[i]);   //注意转移方程的变化    cout << f[m] << endl;return 0;
}

AcWing1371. 货币系统 -计数

acwing1371. 货币系统

视频讲解

最初写法(未优化)

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=30,M=10010;int n,m;
LL f[N][M];//状态表示：f[i][j]所有从i-1中选，且总钱数为j的方案数的集合
//(属性：数量) 
int v[N]; //第i种硬币的面值 int main()
{cin>>n>>m;for(int i=1;i<=n;i++) 	cin>>v[i];	//第i种硬币//初始化---for(int i=0;i<=n;i++)f[i][0]=1;//从前i个物品中选，且总钱数为0的方案的集合--属性-计数=1(什么都不选-仅这一种方案)for(int j=1;j<=m;j++)f[0][j]=0;//从前0个物品中选，且总钱数为j的方案的集合--属性-计数=0(没有方案)//状态计算for(int i=1;i<=n;i++)//第i种硬币 {for(int j=0;j<=m;j++)//几元钱 {//状态转移方程：f[i][j]=f[i-1][j]+f[i][j-v]（其中第二项只有当j>v的时候才存在） f[i][j]=f[i-1][j];//如果第i中硬币一个都不选if(j>=v[i]) f[i][j]=f[i-1][j]+f[i][j-v[i]]; } }cout<<f[n][m]<<endl;return 0;
}

一维优化

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=30,M=10010;int n,m;
LL f[M];int v[N]; int main()
{cin>>n>>m;for(int i=1;i<=n;i++) 	cin>>v[i];	//初始化---f[0]=1;//注意初始值的设定//状态计算for(int i=1;i<=n;i++)for(int j=v[i];j<=m;j++)//注意j的起始值f[j]=f[j]+f[j-v[i]]; //注意有变化cout<<f[m]<<endl;return 0;
}

AcWing 900. 整数划分—计数

AcWing 900. 整数划分

完全背包问题模板：for (int i = 1; i <= n; i ++)for (int j = 体积; j <= 背包容量; j ++)f[j] = max (f[j] , f[j - w[i]] + v[i]) ;

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int MOD=1e9+7;
int f[N];int main()
{int n;cin>>n;f[0]=1;for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)f[j]=(f[j]+f[j-i])%MOD;cout<<f[n]<<endl;return 0;
}

AcWing 3382. 整数拆分-计数

AcWing 3382. 整数拆分

#include<bits/stdc++.h>using namespace std;const int N = 1000010, MOD = 1e9;int n;
int f[N];
//int v[N];//v[x]:存储2的x次方
//int w[N];因为是计数dp---所以没有w[N]这一项
int main()
{scanf("%d", &n);f[0] = 1;//初始化//for(int i = 1; i<=n; i++)//for(int j = v[i]; j<=m; j++)//        f[j] = max(f[j],f[j-v[i]]+w[i]);for (int i = 1; i <= n; i *= 2)//这里的i=v[x]:存储2的x次方for (int j = i; j <= n; j ++ )f[j] = (f[j] + f[j - i]) % MOD;cout << f[n] << endl;return 0;
}

线性DP

数字三角形模型

AcWing 898. 数字三角形

AcWing 898. 数字三角形

从底至上

#include<bits/stdc++.h>
using namespace std;
const int N=510;int w[N][N];//存储数据 
int f[N][N];//dp数组：---状态表示：从底向上走到[i][j]的集合--属性--maxint main()
{int n;cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)cin>>w[i][j];//初始化一下dp数组的最后一行---最后一层for(int i=1;i<=n;i++)f[n][i]=w[n][i];//状态计算-----集合划分 ---划分依据---一般是取最后一个点 for(int i=n-1;i>0;i--)for(int j=1;j<=i;j++)//状态转移方程f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);//从下一层的左边--或者--下一层的右边 cout<<f[1][1]<<endl;} 

从上到下

#include<bits/stdc++.h>
using namespace std;
const int N = 510,INF = 0x3f3f3f3f;
int f[N][N];
int a[N][N];int main(){int n;cin >> n;for(int i = 1;i <= n;i++){for(int j = 1;j <= i;j++){cin >> a[i][j];}}memset(f,-INF,sizeof(f));//将状态数组初始化为-INF---解决了边界问题f[1][1] = a[1][1];for(int i = 2;i <= n;i++){for(int j = 1;j <= i;j++){f[i][j] = max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);}}int ans=-INF;//遍历最后一行，找到最大值，输出即可for(int i = 1;i <= n;i++)ans=max(ans,f[n][i]);cout<<ans<<endl;return 0;
}

AcWing 3304. 数字三角形

AcWing 3304. 数字三角形
从上到下dp

#include<bits/stdc++.h>
using namespace std;
const int N = 110,INF = 0x3f3f3f3f;
int f[N][N];
int a[N][N];int main(){int n;cin >> n;for(int i = 1;i <= n;i++){for(int j = 1;j <= i;j++){cin >> a[i][j];}}memset(f,-INF,sizeof(f));f[1][1] = a[1][1];for(int i = 2;i <= n;i++){for(int j = 1;j <= i;j++){f[i][j] = max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);}}if(n%2!=0)//当最后一层是奇数时 cout<<f[n][n/2+1]<<endl;else cout<<max(f[n][n/2],f[n][n/2+1])<<endl;return 0;
}

AcWing1015. 摘花生

AcWing1015. 摘花生

#include<bits/stdc++.h>
using namespace std;
const int N=110;int a[N][N];
int f[N][N];int T;
int R,C;
int main()
{cin>>T;while(T--){cin>>R>>C;memset(a,0,sizeof(a));//重置一下数组---因为要多组输入 memset(f,0,sizeof(f));for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)cin>>a[i][j];for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];//状态计算 cout<<f[R][C]<<endl;}return 0;} 

最长上升子序列模型

AcWing 895. 最长上升子序列(非下降子序列）

AcWing 895. 最长上升子序列

集合的划分f[i]的倒数第二个数的位置—来划分

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;int n;
int a[N];
int f[N];//状态表示：所有以i结尾的最长上升子序列的长度
//属性：max ---子序列---从前往后挑数---也可以隔着挑 int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)f[i]=1;//初始化一下dp数组   一开始的时候，这个新子序列只有a[i]这一个元素 for(int i=1;i<=n;i++)for(int j=1;j<=i-1;j++)//遍历a[i]之前的元素if(a[j]<a[i])//上升---要保证 f[i]=max(f[i],f[j]+1);int ans=1;//找出最大值 for(int i=1;i<=n;i++)ans=max(ans,f[i]);cout<<ans<<endl;return 0;
} 

AcWing482. 合唱队形(最长上升子序列的变形)

AcWing482. 合唱队形

#include<bits/stdc++.h>
using namespace std;
const int N=110;int n;
int w[N];
int f[N];//状态表示：所有以i结尾的最长上升子序列---从前向后 
//属性：max int g[N];//状态表示：所有以i开始的最长下降子序列---从后向前
//属性：maxint main()
{cin>>n;for(int i=1;i<=n;i++)cin>>w[i];//所有以第i个元素结尾的最长上升子序列的长度max for(int i=1;i<=n;i++){f[i]=1;//初始时-以i结尾的--子序列最大长度为1 for(int j=1;j<i;j++){if(w[j]<w[i])//如果i可以作为j结尾子序列的下一个时---更新 f[i]=max(f[i],f[j]+1); }}//所有以第i个元素开始的最长下降子序列的长度maxfor(int i=n;i>=1;i--){g[i]=1;//初始时-以i结尾的--子序列最大长度为1 for(int j=n;j>i;j--){if(w[i]>w[j])//如果i可以作为j结尾子序列的下一个时---更新g[i]=max(g[i],g[j]+1); }}int ans=0;//枚举一下求一个最大值 for(int k=1;k<=n;k++){ans=max(ans,f[k]+g[k]-1);//因为最高的小朋友被计算了两次 }cout<<n-ans<<endl;return 0;} 

公共子序列

AcWing 897. 最长公共子序列(模板题)

AcWing 897. 最长公共子序列
子序列—不一定连续

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int M=1e3+10;int n,m;
char a[N];
char b[M];
int f[N][M];int main()
{cin>>n>>m;cin>>a+1;//为了方便处理---读入从[1,n] cin>>b+1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//这两个状态一定有 f[i][j]=max(f[i-1][j],f[i][j-1]);if(a[i]==b[j])//当末尾字符相同时 f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}cout<<f[n][m]<<endl;return 0;
}

序列和

AcWing 3393. 最大序列和

AcWing 3393. 最大序列和

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n;
LL w[N];//
LL f[N];//状态表示：所有以i为右端点的区间(非空连续序列)的集合
//属性：max
int main()
{cin>>n; LL res = -1e18;for (int i = 1; i<= n; i ++ )cin>>w[i];for (int i = 1; i <= n; i ++ ){f[i]=max(f[i-1]+w[i],w[i]);//状态转移方程res=max(res,f[i]);//更新答案} cout<<res<<endl;  	return 0;
}

AcWing 1051. 最大的和

acwing 1051. 最大的和

本题使用一个常用技巧: 前后缀分解
该技巧的常用套路如下：
1. 求前缀数组
2. 求后缀数组
3. 枚举前后缀数组的分界点对于本题，可以分解为求连续数组前缀和的最大值和， 求连续数组后缀和的最大值
可以定义如下：f[i]: 从1~i从前往后枚举，以数字a[i]结尾的，连续和的最大值
g[j]: 从n~j从后往前枚举，以数字a[j]结尾的，连续和的最大值f_max[i]: 从1~ i从前往后枚举，前1~j个数字连续和的最大值
g_max[j]: 从n~ j从后往前枚举，后n~j个数字连续和的最大值最后枚举前后缀数组的分界点总体时间复杂度: O(N)

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int INF=0x3f3f3f3f;
int T,n;int w[N];
int f[N];//状态表示：所有以i为区间右端点的集合 
int f_max[N];//状态表示：[1,i]范围内---连续和的最大值 int g[N];//状态表示：所有以i为区间左端点的集合---连续和---[x,i]:x可以取1,2,3,4，，，，，i 
int g_max[N];//状态表示：[i,n]范围内---某一个连续和---的最大值int main()
{cin>>T;while(T--){memset(w,0,sizeof(w));memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(f_max,-INF,sizeof(f_max));memset(g_max,-INF,sizeof(g_max));//这里 [i,n]范围内---连续和的最大值---一定要初始化为-无穷 cin>>n;for(int i=1;i<=n;i++)cin>>w[i];for(int i=1;i<=n;i++){f[i]=max(f[i-1]+w[i],w[i]);f_max[i]=max(f_max[i-1],f[i]);//数组中前i个数据的最大和为f_max[i]	}for(int i=n;i>=1;i--){g[i]=max(g[i+1]+w[i],w[i]);g_max[i]=max(g[i+1],g[i]);//数组中后n-j个数据的最大和为g_max[j]}int ans=-1e5;for(int i=1;i<n;i++)ans=max(ans,f_max[i]+g_max[i+1]);cout<<ans<<endl;}return 0;
}

区间DP

AcWing282. 石子合并—如果是任取两堆—哈弗曼编码

acwing282. 石子合并

AcWing 282. 石子合并（区间 DP 模版题详解分析）

#include<bits/stdc++.h>
using namespace std;
const int N=310;
const int INF=0x3f3f3f3f;
int f[N][N];//dp数组 		---状态表示： f[i][j]:所有将[i,j]这个区间合并成一堆的方案的集合
int a[N];//存储石子大小 
int s[N];//一维前缀和数组 
//属性：min 
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=a[i]+s[i-1];//前缀和初始化 }memset(f,INF,sizeof(f));//----初始化dp数组---因为dp属性：min 所有初始化为 +00//区间dp---第一维-区间长度(区间中点的数量)---第二维-区间[l,r]左端点l---第三维-区间分割点kfor(int len=1;len<=n;len++) for(int l=1;l+len-1<=n;l++){int r=l+len-1;//由区间左端点+区间长度得区间右端点if(len==1)//区间仅有一堆时 {f[l][r]=0; continue;}//这里k枚举的是左半边最后一个石子的位置	for(int k=l;k+1<=r;k++)//将区间分隔为[l,k],[k+1,r]---k可以等于l此时[l,k(l)]仅一堆 f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+(s[r]-s[l-1]));			  	}cout<<f[1][n]<<endl;//状态表示的属性为所有将[i,j]堆成一堆的代价最小值return 0;} 

201612-4-csp-压缩编码—与石子合并代码一样

AcWing 3240. 压缩编码

AcWing 3240. 压缩编码 哈夫曼树与区间DP的区别+绘图理解

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int INF=0x3f3f3f3f;
int n;
int a[N];
int s[N];//前缀和数组 int f[N][N];//表示从[l,r]表示从l到r合并的最小花费
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];}//区间dp问题---第一维：区间长度---第二维：区间左端点---第三维：分割点Kmemset(f,INF,sizeof(f));for(int len=1;len<=n;len++)for(int l=1;l+len-1<=n;l++){int r=l+len-1;if(len==1){f[l][r]=0;continue;}for(int k=l;k+1<=r;k++){f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+(s[r]-s[l-1]));}} cout<<f[1][n]<<endl;return 0;} 

数位统计DP

状态压缩DP

树形DP

记忆化搜索

第六讲 贪心算法

区间合并

AcWing 803. 区间合并—区间左端点排序

AcWing 803. 区间合并

贪心按左端点水过
思路：就是以左端点进行排序，每次让下一个集合与该集合的右端点进行比较即可。小心--------经典的错误，标准的零分

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{int l;int r;bool operator<(const node& t)const //重载小于号- {return l<t.l;}
}q[N]; 
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;q[i]={l,r};}sort(q,q+n);//按区间的左端点从小到大排序int res=0;//答案 int ed=-2e9;//区间右端点 for(int i=0;i<n;i++){if(q[i].l<=ed)//当某一区间左端点<=上一区间右端点 -----两个区间合并 {//ed=q[i].r;-------经典的错误，标准的零分----还不能确定ed和q[i].r谁大 ed=max(ed,q[i].r); }else//当某一区间的左端点>上一区间的右端点时 ---------两个区间不能合并 {res++;ed=q[i].r;}} cout<<res<<endl; return 0;
}

AcWing 422. 校门外的树—区间左端点排序

AcWing 422. 校门外的树

视频讲解

朴素写法

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 10010;int n, m;
bool st[N];int main()
{scanf("%d%d", &m, &n);while (n -- ){int l, r;scanf("%d%d", &l, &r);for (int i = l; i <= r; i ++ ) st[i] = true;}int res = 0;for (int i = 0; i <= m; i ++ )if (!st[i])res ++ ;printf("%d\n", res);return 0;
}

pair数组写法

#include <iostream>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 110;
#define x first
#define y secondint n, m;
PII seg[N];int main()
{cin >> m >> n;for (int i = 0; i < n; i ++ ) cin >> seg[i].x >> seg[i].y;sort(seg, seg + n);int res = m + 1;int st = seg[0].x, ed = seg[0].y;for (int i = 1; i < n; i ++ )if (seg[i].x <= ed) ed = max(seg[i].y, ed);else{res -= ed - st + 1;st = seg[i].x, ed = seg[i].y;}res -= ed - st + 1;cout << res << endl;return 0;
}

结构体写法

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;int m, n;
struct Segment
{int l, r;bool operator< (const Segment& t) const{return l < t.l;}
}seg[N];int main()
{cin >> m >> n;for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;sort(seg, seg + n);int sum = 0;int L = seg[0].l, R = seg[0].r;for (int i = 1; i < n; i ++ )if (seg[i].l <= R) R = max(R, seg[i].r);else{sum += R - L + 1;L = seg[i].l, R = seg[i].r;}sum += R - L + 1;cout << m + 1 - sum << endl;return 0;
}

区间问题

AcWing 905. 区间选点—区间右端点排序

AcWing 905. 区间选点

AcWing 908. 最大不相交区间数量—区间右端点排序

AcWing 908. 最大不相交区间数量

两道题的代码完全一样
最大不相交区间数量=相交区间数量(例如：下图中的123中选择2)+不相交区间数量(例如：下图中的4)=1+1=2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct node{int l;int r;bool operator<(const node& t)const //重载小于号- {return r<t.r;}
}q[N]; 
int n;
int main()
{cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;q[i]={l,r};}sort(q,q+n);//按区间的右端点从小到大排序int res=0;//答案 int ed=-2e9;//区间右端点 for(int i=0;i<n;i++){if(q[i].l>ed)//当某一区间的左端点>上一区间的右端点时 {res++;ed=q[i].r;}} cout<<res<<endl; return 0;
}

AcWing 906. 区间分组—区间左端点排序

AcWing 906. 区间分组
思路

#include<bits/stdc++.h>
#define l first
#define r second
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
PII q[N];//保存N个区间的左右端点 int n;int main()
{cin>>n;for(int i=0;i<n;i++){int x,y;cin>>x>>y;q[i]={x,y}; }sort(q,q+n);//按区间左端点排序priority_queue<int,vector<int>,greater<int>> heap;//定义一个小根堆for(int i=0;i<n;i++){if(heap.empty()||q[i].l<=heap.top())//当堆为空 或者 某一区间左端点≤堆顶元素heap.push(q[i].r);else								//某一区间左端点>堆顶元素时，将该区间加入某一分组中去 {heap.pop();//让所有分组(分组内所有区间的右端点-max )-min的更新---------即加入到该分组中heap.push(q[i].r);} } cout<<heap.size()<<endl;return 0;} 

AcWing 907. 区间覆盖—按区间左端点排序

AcWing 907. 区间覆盖
图解：区间覆盖（按左端点排序，在左端点≤st的情况下，选择右端点最大的区间）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define l first
#define r second
typedef pair<int,int> PII;
PII q[N];int main()
{int n;int st,ed;//定义线段区间的起点和终点cin>>st>>ed;cin>>n;for(int i=0;i<n;i++){int x,y;cin>>x>>y;q[i]={x,y};} sort(q,q+n);//按区间左端点排序 int ans=0;//最少区间数 bool success=false;//有无解for(int i=0;i<n;i++)//遍历所有的区间 ----双指针算法 i,j指针 {int j=i;int maxr=-2e9;while(j<n && q[j].l<=st){maxr=max(maxr,q[j].r);//得到所有左端点≥st，且右端点最靠右的j++; }if(maxr<st)//当目前所有的区间的右端点的max＜st时 {ans=-1;break;//此时无解 }ans++;if(maxr>=ed)// 目前所有的区间的右端点的max＞ed时{success=true;break;//此时返回即可 } st=maxr;//更新线段区间的起点 i=j-1; //跳过这些区间 }if(!success)cout<<-1<<endl;elsecout<<ans<<endl;return 0;} 

Huffman树

AcWing 148. 合并果子

AcWing 148. 合并果子

我们可以用贪心的方法，让每次合并的两堆果子的数量都尽可能小，取当前h中的两个最小值，合并。则每次合并消耗的体力最少，总消耗体力就最少，记录体力的同时，还要将产生的新果子堆重新插入。既然有了取最小值与插入新堆两个操作，我们就想到了用小根堆。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;int main()
{int n;cin>>n;//定义一个小根堆 priority_queue<int,vector<int>,greater<int>> heap;while(n--){int x;cin>>x;heap.push(x);//将果子输入小根堆 }int ans=0;while(heap.size()>1)//除非小根堆中仅有一堆果子 {auto x=heap.top();//取出最小的一堆果子 heap.pop();auto y=heap.top();//取出次小的一堆果子 heap.pop();ans+=x+y;heap.push(x+y);//}cout<<ans<<endl;return 0;
}

排序不等式

AcWing 913. 排队打水

AcWing 913. 排队打水

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int a[N];
int main()
{int n; cin>>n;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);//从小到大排序LL ans=0;for(int i=0;i<n;i++){ans+=a[i]*(n-i-1);//第i位的打水时间为a[i]，后面(n-1-i)个人需要等待 } cout<<ans<<endl;return 0;
}

绝对值不等式

AcWing 104. 货仓选址

AcWing 104. 货仓选址

#include<bits/stdc++.h>
using namespace std;const int N=1e5+10;
int n;
int a[N];int main()
{cin>>n;for(int i=0;i<n;i++)	cin>>a[i];sort(a,a+n);int res=0;for(int i=0;i<n;i++)	res+=abs(a[i]-a[n/2]);//中位数就是最优解cout<<res<<endl;return 0;} 

推公式

AcWing 125. 耍杂技的牛

AcWing 125. 耍杂技的牛
贪心的证明

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
typedef pair<int,int> PII;
PII q[N]; 
int main()
{int n;cin>>n;for(int i=0;i<n;i++){int w,s;cin>>w>>s;q[i].first=w+s;//贪心证明了这里为什么要这样排序 q[i].second=s;} sort(q,q+n);//最小可能值------出现在当a叠在b上面时 且 Wa+Sa<Wb+Sb时 ---其他牛的危险值显然不变，所以分析交换前后这两头牛中最大的危险值即可。int ans=-2e9;//返回最大的风险值int sum=0;//此时某头牛头上所有牛的总重量for(int i=0;i<n;i++){q[i].first-=q[i].second;//q[i].first保存的仅为第i头牛的重量ans=max(ans,sum-q[i].second);sum+=q[i].first; } cout<<ans<<endl;//输出最大风险值的最小可能值 return 0;
}

AcWing1055. 股票买卖 II

操作分解---满足性质---各自之间互不影响题意
输入一支股票每天的价钱，这只股票可以进行多次买入卖出，求最大利益相关思路
当后一天大于前一天时，在前一天买入，后一天卖出，最后得到的就是最大利益
(一个跨度为多天的交易，都可以用若干个跨度等于一天的交易来计算)

acwing1055. 股票买卖 II(贪心)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int a[N];int main()
{int n;cin>>n;for(int i=0;i<n;i++)	cin>>a[i];LL ans=0;//定义最大利润 for(int i=0;i<n-1;i++)ans+=max(0,a[i+1]-a[i]);//判断要不要买入股票 cout<<ans<<endl;return 0;
}