• 【算法基础】动态规划

    背包问题

    01背包

    每个物品只能放一次

    2. 01背包问题 - AcWing题库

    二维dp

    1. #include
    2. const int N=1010;
    3. int f[N][N];
    4. int v[N],w[N]; 
    5. signed main()
    6. {
    7. 	int n,m;
    8. 	std::cin>>n>>m; 
    9. 	for(int i=1;i<=n;i++) std::cin>>v[i]>>w[i];
    10. 	
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		for(int j=0;j<=m;j++)
    14. 		{
    15. 			f[i][j]=f[i-1][j];
    16. 			if(j>=v[i]) f[i][j]=std::max(f[i][j],f[i-1][j-v[i]]+w[i]);	
    17. 		} 
    18. 	}	
    19. 	std::cout<
    20. 	return 0;
    21. }

    一维dp

    观察上面的循环内的式子，发现推导出f[i][j]只需要f[i-1][j]和f[i-1][j-v[i]]就好，也就是当前的f[i]是由上一层f[i-1]推导而来，因此我们用到滚动数组来对二维dp进行优化。

    滚动数组是一种优化算法技巧，常用于动态规划问题中，用来减少空间复杂度。在动态规划问题中，我们通常需要使用一个数组来存储中间计算的结果，以供后续计算使用。而滚动数组通过利用数组中的部分空间，不断覆盖原来的值，从而减少所使用的空间。

    具体来说，滚动数组通常用一个较小的大小来表示原数组，这个较小的大小是经过推导和分析所确定的。在计算过程中，我们只需要维护这个较小的数组，当需要用到原数组中的值时，通过计算得到。

    这种技巧能够在一定程度上减少使用的空间复杂度，特别是针对一些状态转移方程只与之前的一部分状态有关的情况。滚动数组在动态规划问题中被广泛应用，能够提高算法的效率。

    同时， 原循环中f[i][j]=std::max(f[i][j],f[i-1][j-v[i]]+w[i]);，如果j是正序即从v[i]-m，那么这里的f[j-v[i]]就是f[i][j-v[i]],因为在循环中正序从小到大会覆盖掉之前的f[i-1],故而采取逆序。滚动数组（简单说明）_滚动数组思想-CSDN博客    

    1. #include
    2. const int N=1010;
    3. int f[N];
    4. int v[N],w[N]; 
    5. signed main()
    6. {
    7. 	int n,m;
    8. 	std::cin>>n>>m; 
    9. 	for(int i=1;i<=n;i++) std::cin>>v[i]>>w[i];
    10. 	
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		for(int j=m;j>=v[i];j--)
    14. 		{
    15. 			f[j]=std::max(f[j],f[j-v[i]]+w[i]);	
    16. 		} 
    17. 	}	
    18. 	std::cout<
    19. 	return 0;
    20. }

    完全背包

    物品有无限件

    3. 完全背包问题 - AcWing题库

    三重循环

    额外加一层循环来枚举选择当前项的个数，这样会超时

    1. #include
    2. const int N=1010;
    3. int f[N][N];
    4. int v[N],w[N]; 
    5. signed main()
    6. {
    7. 	int n,m;
    8. 	std::cin>>n>>m; 
    9. 	for(int i=1;i<=n;i++) std::cin>>v[i]>>w[i];
    10. 	
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		for(int j=0;j<=m;j++)
    14. 		{
    15. 			for(int k=0;k*v[i]<=j;k++)
    16. 			{
    17. 				f[i][j]=std::max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    18. 			}
    19. 		}
    20. 	}	
    21. 	std::cout<
    22. 	return 0;
    23. }

     二重循环

    与01背包不同的是max里面是f[i][j-v[i]]+w[i]，01背包中这里是 f[i-1][j-v[i]]+w[i]

    因此下面优化成一维时对j的枚举按升序就好。

    1. #include
    2. const int N=1010;
    3. int f[N][N];
    4. int v[N],w[N]; 
    5. signed main()
    6. {
    7. 	int n,m;
    8. 	std::cin>>n>>m; 
    9. 	for(int i=1;i<=n;i++) std::cin>>v[i]>>w[i];
    10. 	
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		for(int j=0;j<=m;j++)
    14. 		{
    15. 			f[i][j]=f[i-1][j];
    16. 			if(j>=v[i]) f[i][j]=std::max(f[i][j],f[i][j-v[i]]+w[i]);
    17. 		}
    18. 	}	
    19. 	std::cout<
    20. 	return 0;
    21. }

    一维循环 

    1. #include
    2. const int N=1010;
    3. int f[N];
    4. int v[N],w[N]; 
    5. signed main()
    6. {
    7. 	int n,m;
    8. 	std::cin>>n>>m; 
    9. 	for(int i=1;i<=n;i++) std::cin>>v[i]>>w[i];
    10. 	
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		for(int j=v[i];j<=m;j++)
    14. 		{
    15. 			f[j]=std::max(f[j],f[j-v[i]]+w[i]);
    16. 			
    17. 		}
    18. 	}	
    19. 	std::cout<
    20. 	return 0;
    21. }

    多重背包问题 

    物品只有s[i]件

    4. 多重背包问题 I - AcWing题库

     三重循环

    1. #include
    2. const int N=1e3+10;
    3. int v[N],w[N],s[N];
    4. int num,val;
    5. int f[N][N];//从前i件中选，剩余容量为 
    6.  
    7. signed main()
    8. {
    9. 	std::cin>>num>>val;	
    10. 	for(int i=1;i<=num;i++) std::cin>>v[i]>>w[i]>>s[i];
    11. 	
    12. 	for(int i=1;i<=num;i++)//枚举物品 
    13. 	{
    14. 		for(int j=0;j<=val;j++)
    15. 		{
    16. 			for(int k=0;k*v[i]<=j&&k<=s[i];k++)
    17. 			{
    18. 				f[i][j]=std::max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    19. 			}
    20. 		} 
    21. 	}
    22. 	std::cout<
    23. 	return 0;
    24. }

    二进制优化 

     5. 多重背包问题 II - AcWing题库

    1. #include
    2. const int N = 12010, M = 2010;
    3. int v[N], w[N];
    4. int f[M];
    5. int num,val,cnt;
    6. signed main()
    7. {
    8. 	std::cin>>num>>val;
    9. 	for(int i=1;i<=num;i++)
    10. 	{
    11. 		int a,b,s;
    12. 		std::cin>>a>>b>>s;
    13. 		int k=1;
    14. 		while(s>=k)
    15. 		{
    16. 			cnt++;
    17. 			v[cnt]=a*k;
    18. 			w[cnt]=b*k;
    19. 			s-=k;
    20. 			k*=2;	
    21. 		}	
    22. 		if(s) 
    23. 		{
    24. 			cnt++;
    25. 			v[cnt]=a*s;
    26. 			w[cnt]=b*s;
    27. 		}
    28. 	}
    29. 	for(int i=1;i<=cnt;i++)	
    30. 	{
    31. 		for(int j=val;j>=v[i];j--)
    32. 		{
    33. 			f[j]=std::max(f[j],f[j-v[i]]+w[i]);		
    34. 		}
    35. 	}
    36. 	std::cout<
    37. 	return 0;
    38. }

    分组背包问题

    9. 分组背包问题 - AcWing题库

    每组物品有若干个，同一组内的物品最多只能选一个。

    二维dp

    1. #include
    2. const int N=110;
    3.  
    4. int s[N],w[N][N],v[N][N],f[N][N];
    5. int num,val;
    6. signed main()
    7. {
    8. 	std::cin>>num>>val;//组数 
    9. 	for(int i=1;i<=num;i++)
    10. 	{
    11. 		std::cin>>s[i];
    12. 		for(int j=1;j<=s[i];j++)
    13. 		{
    14. 			std::cin>>v[i][j]>>w[i][j];
    15. 		}
    16. 	}
    17. 	for(int i=1;i<=num;i++)
    18. 	{
    19. 		for(int j=0;j<=val;j++)
    20. 		{
    21. 		    f[i][j]=f[i-1][j];
    22. 			for(int k=0;k<=s[i];k++)
    23. 			{
    24. 				if(j>=v[i][k]) f[i][j]=std::max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
    25. 			}
    26. 		} 
    27. 	}
    28. 	std::cout<
    29. 	return 0;
    30. }

     一维dp

    1. #include
    2. const int N=110;
    3.  
    4. int s[N],w[N][N],v[N][N],f[N];
    5. int num,val;
    6. signed main()
    7. {
    8. 	std::cin>>num>>val;//组数 
    9. 	for(int i=1;i<=num;i++)
    10. 	{
    11. 		std::cin>>s[i];
    12. 		for(int j=1;j<=s[i];j++)
    13. 		{
    14. 			std::cin>>v[i][j]>>w[i][j];
    15. 		}
    16. 	}
    17. 	for(int i=1;i<=num;i++)
    18. 	{
    19. 		for(int j=val;j>=0;j--)
    20. 		{
    21. 			for(int k=1;k<=s[i];k++)
    22. 			{
    23. 				if(j>=v[i][k]) f[j]=std::max(f[j],f[j-v[i][k]]+w[i][k]);
    24. 			}
    25. 		} 
    26. 	}
    27. 	std::cout<
    28. 	return 0;
    29. }

    线性DP 

    数字三角形

    898. 数字三角形 - AcWing题库

    1. #include
    2. const int N=510;
    3. int f[N][N],a[N][N];
    4.  
    5. signed main()
    6. {
    7. 	int n;
    8. 	std::cin>>n;
    9. 	for(int i=1;i<=n;i++)
    10. 	{
    11. 		for(int j=1;j<=i;j++) std::cin>>a[i][j];
    12. 	}
    13. 	for(int i=n;i>=1;i--)
    14. 	{
    15. 		for(int j=1;j<=i;j++)
    16. 		{
    17. 			f[i][j]=std::max(f[i+1][j],f[i+1][j+1])+a[i][j];
    18. 		}
    19. 	}
    20. 	std::cout<1][1];
    21. 	return 0;
    22. }

    最长上升子序列

    双重循环

    895. 最长上升子序列 - AcWing题库

    1. #include
    2. const int N=1e3+10;
    3. int a[N],f[N];
    4.  
    5. signed main()
    6. {
    7. 	int n;
    8. 	std::cin>>n;
    9. 	for(int i=1;i<=n;i++) std::cin>>a[i];
    10. 	
    11. 	for(int i=1;i<=n;i++)
    12. 	{
    13. 		f[i]=1;
    14. 		for(int j=1;j
    15. 		{
    16. 			if(a[j]max(f[i],f[j]+1);	
    17. 		}	
    18. 	}
    19. 	int res=-1e9;
    20. 	for(int i=1;i<=n;i++) res=std::max(res,f[i]);
    21. 	std::cout<
    22. 	return 0; 
    23. }

     优化

    1. #include
    2. const int N=1e3+10;
    3. int a[N],q[N];
    4. int n,cnt;
    5. signed main()
    6. {
    7. 	std::cin>>n;
    8. 	for(int i=1;i<=n;i++) std::cin>>a[i];
    9. 	
    10. 	for(int i=1;i<=n;i++)
    11. 	{
    12. 		if(a[i]>q[cnt]||!cnt) q[++cnt]=a[i];//q从1开始 
    13. 		else{
    14. 			int l=1,r=cnt,res=-1;
    15. 			while(l<=r)
    16. 			{
    17. 				int mid=l+r>>1;
    18. 				if(q[mid]>=a[i]) 
    19. 				{
    20. 					res=mid;
    21. 					r=mid-1;
    22. 				}else l=mid+1;
    23. 			}  
    24. 			q[res]=a[i];
    25. 		} 
    26. 		
    27. 	}
    28. 	std::cout<
    29. 	return 0; 
    30. }

    最长公共子序列

    897. 最长公共子序列 - AcWing题库

    1. #include
    2. const int N=1e3+10;
    3. char a[N],b[N];
    4. int n,m;
    5. int f[N][N];
    6. signed main()
    7. {
    8.     std::cin>>n>>m;
    9.     std::cin>>a+1>>b+1;
    10.     for(int i=1;i<=n;i++)
    11.     {
    12.         for(int j=1;j<=m;j++)
    13.         {
    14.             f[i][j]=std::max(f[i-1][j],f[i][j-1]);
    15.             if(a[i]==b[j]) f[i][j]=std::max(f[i][j],f[i-1][j-1]+1);
    16.         }
    17.     }
    18.     std::cout<
    19.     return 0;
    20. }

    最短编辑距离

    902. 最短编辑距离 - AcWing题库

    1. #include
    2. const int N=1e3+10;
    3. char a[N],b[N];
    4. int n,m;
    5. int f[N][N];
    6. signed main()
    7. {
    8.     std::cin>>n>>a+1>>m>>b+1;
    9.     for(int i=0;i<=n;i++) f[i][0]=i;
    10.     for(int j=0;j<=m;j++) f[0][j]=j;
    11.     
    12.     for(int i=1;i<=n;i++)
    13.     {
    14.         for(int j=1;j<=m;j++)
    15.         {
    16.             f[i][j]=std::min(f[i-1][j],f[i][j-1])+1;//增，删的情况
    17.             if(a[i]==b[j]) f[i][j]=std::min(f[i][j],f[i-1][j-1]);
    18.             else f[i][j]=std::min(f[i][j],f[i-1][j-1]+1);//判断是否需要改
    19.         }
    20.     }
    21.     std::cout<
    22.     return 0;
    23. }

    编辑距离

    899. 编辑距离 - AcWing题库

    给定n个字符串，m次询问每次给一个字符串和限制，问每次询问中n个字符串中每次有多少个可以在操作限制内改为给的字符

    这里发现f数组中，前面是枚举给定字符串还是要修改的字符串不会影响答案。 

    1. #include
    2. const int N=1e3+10;
    3. int n,m;
    4. char s[N][15];
    5. int f[N][N];
    6. /*
    7. int dis(char a[],char s[])//把s变成a 
    8. {
    9. 	int la=strlen(a+1),ls=strlen(s+1);
    10. 	for(int i=0;i<=la;i++) f[i][0]=i;
    11. 	for(int i=0;i<=ls;i++) f[0][i]=i;
    12. 	
    13. 	for(int i=1;i<=la;i++)
    14. 	{
    15. 		for(int j=1;j<=ls;j++)
    16. 		{
    17. 			f[i][j]=std::min(std::min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+!(a[i]==s[j]));		
    18. 		}
    19. 	} 
    20. 	return f[la][ls];
    21. }*/
    22. int dis(char a[],char s[])//把s变成a 
    23. {
    24. 	int la=strlen(a+1),ls=strlen(s+1);
    25. 	for(int i=0;i<=ls;i++) f[i][0]=i;
    26. 	for(int i=0;i<=la;i++) f[0][i]=i;
    27. 	
    28. 	for(int i=1;i<=ls;i++)
    29. 	{
    30. 		for(int j=1;j<=la;j++)
    31. 		{
    32. 			f[i][j]=std::min(std::min(f[i-1][j]+1,f[i][j-1]+1),f[i-1][j-1]+!(s[i]==a[j]));		
    33. 		}
    34. 	} 
    35. 	return f[ls][la];
    36. }
    37. signed main()
    38. {
    39. 	std::cin>>n>>m;
    40. 	for(int i=0;i>s[i]+1;//给定的字符串
    41. 	while(m--)
    42. 	{
    43. 		char a[N];
    44. 		int limit;
    45. 		std::cin>>a+1>>limit;
    46. 		
    47. 		int res=0;
    48. 		for(int i=0;i//枚举有几个字符串可以变成询问的 
    49. 		{
    50. 			if(dis(a,s[i])<=limit) res++;
    51. 		}	
    52. 		std::cout<'\n';
    53. 	} 
    54. 	
    55. 	return 0;
    56. }

    区间DP

    石子合并

    282. 石子合并 - AcWing题库

    1. #include
    2. const int N=310;
    3. int n;
    4. int a[N],s[N],f[N][N];
    5. signed main()
    6. {
    7. 	std::cin>>n;
    8. 	for(int i=1;i<=n;i++)
    9. 	{
    10. 		std::cin>>a[i];
    11. 		s[i]=s[i-1]+a[i];
    12. 	}
    13. 	for(int len=2;len<=n;len++)
    14. 	{
    15. 		for(int i=1;i+len-1<=n;i++)
    16. 		{
    17. 			int j=i+len-1;//右端点
    18. 			f[i][j]=1e9;
    19. 			for(int k=i;k<=j;k++)
    20. 			{
    21. 				f[i][j]=std::min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);	
    22. 			} 
    23. 		}
    24. 	}
    25. 	std::cout<1][n];
    26. 	return 0;
    27. }

    计数类DP

    整数划分 

    900. 整数划分 - AcWing题库

     完全背包
    朴素版
    1. #include
    2. const int N=1e3+10,mod=1e9+7;
    3. int f[N][N];//f[i][j]表示只从1~i中选，且总和等于j的方案数
    4. signed main()
    5. {
    6. 	int n;
    7. 	std::cin>>n;
    8. 	f[0][0]=1;
    9. 	
    10. 	for(int i=1;i<=n;i++)
    11. 	{
    12. 		for(int j=0;j<=n;j++)
    13. 		{
    14. 			f[i][j]=f[i-1][j];
    15. 			if(j>=i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
    16. 		}
    17. 	}
    18. 	std::cout<
    19. 	return 0;
    20. }
    优化版
    1. #include
    2. const int N=1e3+10,mod=1e9+7;
    3. int f[N];//f[i][j]表示只从1~i中选，且总和等于j的方案数
    4. signed main()
    5. {
    6. 	int n;
    7. 	std::cin>>n;
    8. 	f[0]=1;
    9. 	
    10. 	for(int i=1;i<=n;i++)
    11. 	{
    12. 		for(int j=i;j<=n;j++)
    13. 		{
    14. 			f[j]=(f[j]+f[j-i])%mod;
    15. 		}
    16. 	}
    17. 	std::cout<
    18. 	return 0;
    19. }

    数位统计DP

    计数问题

    338. 计数问题 - AcWing题库

    1. #include
    2. int get(std::vector<int> nums,int l,int r)
    3. {
    4. 	int res=0;
    5. 	for(int i=r;i>=l;i--)
    6. 	{
    7. 		res=res*10+nums[i];
    8. 	}
    9. 	return res;
    10. }
    11. int count(int n,int x)//1-n中，x出现次数 
    12. {
    13. 	if(!n) return 0; 
    14. 	std::vector<int> nums;//倒着存数
    15. 	while(n)
    16. 	{
    17. 		nums.push_back(n%10);
    18. 		n/=10;
    19. 	}//346,643
    20. 	n=nums.size();
    21. 	int res=0;
    22. 	//如果x为0，x不能出现在首位，故而从n-2开始 
    23. 	for(int i=n-1-!x;i>=0;i--) //枚举x出现在每位的次数 
    24. 	{
    25. 		if(i-1)//如果当前位不是最高位，计算前面的可能个数 
    26. 		{
    27. 			res+=get(nums,i+1,n-1)*pow(10,i); //get从低位到高位
    28. 			if(!x) res-=pow(10,i);//如果x为0，前面必须从001开始，因此少一种情况 
    29. 		} 
    30. 		if(nums[i]==x) res+=get(nums,0,i-1)+1; //计算后面的可能 
    31. 		else if(nums[i]>x) res+=pow(10,i);
    32. 	} 
    33. 	return res;
    34. }
    35. signed main()
    36. {
    37. 	int a,b;
    38. 	while(std::cin>>a>>b,a)
    39. 	{
    40. 		if(a>b) std::swap(a,b);
    41. 		for(int i=0;i<10;i++)
    42. 		{
    43. 			std::cout<<count(b,i)-count(a-1,i)<<' ';
    44. 		}
    45. 		std::cout<<'\n';
    46. 	}
    47. 	
    48. 	return 0;
    49. }

    状态压缩DP

    蒙德里安的梦想 

    291. 蒙德里安的梦想 - AcWing题库

    1. #include
    2. const int N=1<<12;//每一列的状态数
    3. bool st[N];//记录合法的列的状态 
    4. #define int long long
    5. std::vector<int> can[N];
    6. int f[12][N];//前i-1列已经填好，且从第i-1列伸到第i列的状态是j 
    7. signed main()
    8. {
    9. 	int n,m;	
    10. 	while(std::cin>>n>>m,n||m)
    11. 	{
    12. 		//先预处理出第i-1列的所有合法状态
    13. 		//先判断是否合法 
    14. 		for(int i=0;i<1<//每一列有n个格子，枚举状态 
    15. 		{
    16. 			int cnt=0;
    17. 			bool ok=true;
    18. 			for(int j=0;j
    19. 			{
    20. 				if((i>>j)&1)//当前位填了 
    21. 				{
    22. 					if(cnt%2)//空格数是奇数 
    23. 					{
    24. 						ok=false;
    25. 						break;
    26. 					} 
    27. 					cnt=0; //归0 
    28. 				}else{
    29. 					cnt++;
    30. 				}
    31. 			}
    32. 			if(cnt%2) ok=false;
    33. 			st[i]=ok;
    34. 		} 
    35. 		memset(can,0,sizeof can);
    36. 		//预处理出所有第i列前一列的可能状态
    37. 		for(int i=0;i<1<//枚举这一列的状态 
    38. 		{
    39. 			for(int j=0;j<1<//前一列的状态 
    40. 			{
    41. 				if((i&j)==0&&st[i|j]) //没有冲突且空格数为偶数 
    42. 				{
    43. 					can[i].push_back(j);	
    44. 				} 
    45. 			} 
    46. 		} 
    47. 		memset(f,0,sizeof f);
    48. 		f[0][0]=1;
    49. 		for(int i=1;i<=m;i++)//枚举每一列 
    50. 		{
    51. 			for(int j=0;j<1<//这一列的状态 
    52. 			{
    53. 				for(auto k:can[j])
    54. 				{
    55. 					f[i][j]+=f[i-1][k]; 
    56. 				} 
    57. 			}
    58. 		} 
    59. 		std::cout<0]<<'\n';
    60. 	}
    61. 	
    62. 	return 0;
    63. }

     最短Hamilton路径

    91. 最短Hamilton路径 - AcWing题库

    1. #include
    2. const int N=1<<20;
    3. int w[25][25],f[N][25];
    4.  
    5. signed main()
    6. {
    7. 	int n;
    8. 	std::cin>>n;
    9. 	for(int i=0;i
    10. 	{
    11. 		for(int j=0;j
    12. 		{
    13. 			std::cin>>w[i][j];
    14. 		}
    15. 	}
    16. 	memset(f,0x3f,sizeof f);
    17. 	f[1][0]=0;
    18. 	for(int i=0;i<1<
    19. 	{
    20. 		for(int j=0;j
    21. 		{
    22. 			if((i>>j)&1)
    23. 			{
    24. 				for(int k=0;k
    25. 				{
    26. 					if((i>>k)&1) f[i][j]=std::min(f[i][j],f[i-(1<
    27. 				}
    28. 			}
    29. 		}
    30. 	}
    31. 	std::cout<1<-1][n-1];
    32. 	return 0;
    33. }

    树形DP

    没有上司的舞会

    285. 没有上司的舞会 - AcWing题库

    1. #include
    2. const int N=6010;
    3.  
    4. int f[N][2],happy[N];
    5. bool hasfa[N];
    6. int h[N],ne[N],e[N],idx;
    7. void add(int a,int b)
    8. {
    9. 	e[idx]=a,ne[idx]=h[b],h[b]=idx++;
    10. }
    11. void dfs(int u)
    12. {
    13. 	f[u][1]=happy[u];
    14. 	for(int i=h[u];i!=-1;i=ne[i])
    15. 	{
    16. 		int j=e[i];
    17. 		dfs(j);
    18. 		f[u][1]+=f[j][0];
    19. 		f[u][0]+=std::max(f[j][0],f[j][1]); 
    20. 	}
    21. 	
    22. }
    23. signed main()
    24. {
    25. 	int n;
    26. 	std::cin>>n;
    27. 	for(int i=1;i<=n;i++) std::cin>>happy[i];
    28. 	memset(h,-1,sizeof h);
    29. 	for(int i=1;i
    30. 	{
    31. 		int a,b;//b是上司
    32. 		std::cin>>a>>b;
    33. 		add(a,b);
    34. 		hasfa[a]=true;	 
    35. 	} 
    36. 	int root=1;
    37. 	while(hasfa[root]) root++;
    38. 	dfs(root);
    39. 	std::cout<max(f[root][0],f[root][1]);
    40. 	return 0;
    41. }

     记忆化搜索

    滑雪

    901. 滑雪 - AcWing题库

    1. #include
    2. const int N=310;
    3. int h[N][N],mem[N][N];
    4. int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
    5. int n,m;
    6. int dfs(int x,int y)
    7. {
    8. 	int &u=mem[x][y];
    9. 	if(u!=-1) return mem[x][y];
    10. 	u=1;//至少可以走当前点 
    11. 	for(int i=0;i<4;i++)
    12. 	{
    13. 		int a=x+dx[i],b=y+dy[i];
    14. 		if(a>=1&&b>=1&&a<=n&&b<=m&&h[a][b]
    15. 			u=std::max(u,dfs(a,b)+1);
    16. 	}
    17. 	return u;
    18. }
    19. signed main()
    20. {
    21. 	std::cin>>n>>m;
    22. 	for(int i=1;i<=n;i++)
    23. 	{
    24. 		for(int j=1;j<=m;j++) std::cin>>h[i][j]; 
    25. 	}
    26. 	memset(mem,-1,sizeof mem);
    27. 	int res=0;
    28. 	for(int i=1;i<=n;i++)
    29. 	{
    30. 		for(int j=1;j<=m;j++)
    31. 		{
    32. 			res=std::max(res,dfs(i,j));
    33. 		}
    34. 	}
    35. 	std::cout<
    36. 	return 0;
    37. }

    完结，撒花~

  • 相关阅读:
    [附源码]java毕业设计心理测评系统
    微服务架构最佳实践：故障恢复和容错策略
    Python——BeautifulSoup库
    4路光栅尺磁栅尺编码器解码转换5MHz高速差分信号转Modbus TCP网络模块 YL97-RJ45
    安装k8s
    谷歌最新开源大模型 Gemma，采用与创建 Gemini 模型相同的研究和技术，专为负责任的人工智能开发而设计。
    Java Number & Math 类
    【企业级SpringBoot单体项目模板 】—— 一些开发规范
    The significance of void 0 in JS
    【OpenPLC学习】RK3568上运行OpenPLC
  • 原文地址：https://blog.csdn.net/m0_74183164/article/details/134116089