3.21小题总结

第一题：生日蛋糕

题解：这题是蛋糕结构是一层一层的，估计很多人很快就能想到是dfs，但是这题的难想的点在于

你每层的状态该怎么去确定，你怎么来确定每层的半径和高度是多少，一开始我也不知很理解，直到在网上看到了一篇大佬的博客才让我茅塞顿开，我干嘛非要确定呢，全用最小的不就好了，因此我们要写出每层的最小的体积和面积，然后用前缀和累加起来，然后三个剪枝（代码里有注释）减少运算，就可以愉快的AC了

#include<iostream>
#include<cstring>
#include<cstdio>
#include <queue>
#include<math.h>
using namespace std;
int n,m;
int sums[16];
int sumv[16];
int sum=0x7fffffff;//记录最小的值 

void dfs(int t,int s,int v,int r,int h)
{
	if(t==0)
	{
		if(s<sum&&v==n)
		{
			sum=s;
		}
		return ;
	}
	if(s+sums[t]>sum)//第一个剪枝，你目前的面积，加上上面层的最小的面积>已知面积，可以直接跳过
	return ;
	if(v+sumv[t]>n)//第二个剪枝，你目前的体积，加上上面层的最小的体积>要求的体积，可以直接跳过
	return ;
	if(s+2*(n-v)/r>sum)//第三个剪枝，你把所有体积都做成一层蛋糕，如果面积>已知面积，跳过
	return ;
	for(int i=r-1;i>=t;i--)
	{
		if(t==m)
		s=i*i;
		int h1=min(h-1,(n-v-sumv[t-1])/(i*i));
		for(int j=h1;j>=t;j--)
		{
			dfs(t-1,s+2*i*j,v+i*i*j,i,j);
		}
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		sumv[i]+=sumv[i-1]+i*i*i;
		sums[i]+=sums[i-1]+2*i*i;
	}
	dfs(m,0,0,sqrt((double)n)+1,n);
	if(sum==0x7fffffff)
	{
		printf("0");
		return 0;
	}
	printf("%d",sum);
	return 0;
}

第二题：速算24

题解：这题一开始也卡了我好久，我一直不明白哪里错了，后面问了学长，但是还是自己想出来为什么错了，因为有可能二三进行运算，这样的话，就会漏掉情况，所以一开始一直过不了，然后写出来了，还用到了全排列函数（不会的可以去了解一下），AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
 
char s[5]={0};
int num[5]={0};
int flag=0;
 
 
void dfs(int sum,int count,int nextt)
{
	if(flag==1)
	return ;
	if(count==3)
	{
		if(sum+nextt==24)
		flag=1;
		if(sum-nextt==24)
		flag=1;
		if(sum*nextt==24)
		flag=1;
		if(nextt!=0&&sum%nextt==0&&sum/nextt==24)
		flag=1;
		return ;
	}
	   
   dfs(sum+nextt,count+1,num[count+1]);
   dfs(sum-nextt,count+1,num[count+1]);
   dfs(sum*nextt,count+1,num[count+1]);
   if(nextt!=0&&sum%nextt==0)
   {
     dfs(sum/nextt,count+1,num[count+1]);
   }
   dfs(sum,count+1,nextt+num[count+1]);
   dfs(sum,count+1,nextt-num[count+1]);
   dfs(sum,count+1,nextt*num[count+1]);
   if(num[count+1]!=0&&nextt%num[count+1]==0)
   {
     dfs(sum,count+1,nextt/num[count+1]);
   }
//	dfs(sum+nextt,count+1,num[count+1]);
//	dfs(sum-nextt,count+1,num[count+1]);
//	dfs(sum*nextt,count+1,num[count+1]);
//	if(sum%nextt==0&&nextt!=0)
//	{
//		dfs(sum/nextt,count+1,num[count+1]);
//	}
//	dfs(sum,count+1,nextt+num[count+1]);
//	dfs(sum,count+1,nextt-num[count+1]);
//	dfs(sum,count+1,nextt*num[count+1]);
//	if(nextt%num[count+1]==0&&num[count+1]!=0)
//	{
//		dfs(sum,count+1,nextt/num[count+1]);
//	}
}
 
 
 
 int main()
{

    while (~scanf("%s", s))
    {
        flag = 0;
        if (strlen(s) == 2)
            num[0] = 10;
        else
        {
            if (s[0] == 'A')
                num[0] = 1;
            else if (s[0] == 'J')
                num[0] = 11;
            else if (s[0] == 'Q')
                num[0] = 12;
            else if (s[0] == 'K')
                num[0] = 13;
            else
                num[0] = s[0] - '0';
        }
        for (int i = 1; i < 4; i++)
        {
            scanf("%s", s);
            if (strlen(s) == 2)
                num[i] = 10;
            else
            {
                if (s[0] == 'A')
                    num[i] = 1;
                else if (s[0] == 'J')
                    num[i] = 11;
                else if (s[0] == 'Q')
                    num[i] = 12;
                else if (s[0] == 'K')
                    num[i] = 13;
                else
                    num[i] = s[0] - '0';
            }
        }
        flag=0;
       sort(num,num+4);
       do
       {
       	 dfs(num[0],1,num[1]);
	   }
	   while(next_permutation(num,num+4)&&flag==0);
        if (flag == 1)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}