您现在的位置是：首页 > 后端

当前栏目

[算法课]实验课全题目详解

算法详解题目

2023-09-11 14:18:49 时间

第一部分递归

第一题数的计算

/*
s=0 n=1 0; s=1 n=1 1;
s=2 n=2 exm:12,2,s=3 n=2 exm:13,1;
s=4 n=4 exm:14,13,24,124;s=5 n=4 exm:15,25,125,5;
s=5 n=3 

观察发现：
if n%2==1 ansN=ansN-1
else ansN+=ansN(N/2)
*/
#include <iostream>

using namespace std;
const int N=1e4;
int f[N];
int main()
{
    f[1]=1;
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
        if(i%2==1)f[i]=f[i-1];
        else f[i]=f[i-1]+f[i/2];
    
    cout<<f[n];
    return 0;
}

在这里插入图片描述

#include<iostream>

using namespace std;

int res=0;

void dfs(int n)
{
    res++;
    for(int i=1;i<=n/2;i++)dfs(i); 
}

int main()
{
    int n;
    cin>>n;
    
    dfs(n);
    
    cout<<res;
    
    return 0 ;
}

在这里插入图片描述

第二题选数

#include<iostream>
#include<cmath>

using namespace std;

const int N=1e4;

int a[N];
int ans;
int n,k;

bool isPrime(int n)
{
    for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;
    return true;
}

void dfs(int u,int sum,int idx)
{
    if(u==k)
    {
        if(isPrime(sum))ans++;
    }
    else
    {
        for(int i=idx;i<n;i++)
            dfs(u+1,sum+a[i],i+1);
    }
}

int main()
{
    cin>>n>>k;
    
    for(int i=0;i<n;i++)cin>>a[i];
    
    dfs(0,0,0);
    
    cout<<ans;
    
    return 0;
}

在这里插入图片描述

#include<iostream>
#include<cmath>

using namespace std;

const int N=1e4;

int a[N];
int ans;
int n,k;

bool isPrime(int n)
{
    for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;
    return true;
}

void dfs(int u,int sum,int idx)
{
    if(u==k)
    {
        if(isPrime(sum))ans++;
        return ;
    }
    
    if(idx>=n)return ;   
    dfs(u,sum,idx+1);
    
    dfs(u+1,sum+a[idx],idx+1);
}

int main()
{
    cin>>n>>k;
    
    for(int i=0;i<n;i++)cin>>a[i];
    
    dfs(0,0,0);
    
    cout<<ans;
    
    return 0;
}

在这里插入图片描述

#include<iostream>
#include<cmath>

using namespace std;

const int N=1e4;

int a[N];
bool st[N];
int ans;
int n,k;
bool RES[N];

bool isPrime(int n)
{
    for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;
    return true;
}

void dfs(int u,int sum)
{
    if(u==k)
    {
        if(isPrime(sum))RES[sum]=true;
        return ;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(st[i]==false)
            {
                st[i]=true;
                dfs(u+1,sum+a[i]);
                st[i]=false;
            }
        }
    }
}

int main()
{
    cin>>n>>k;
    
    for(int i=0;i<n;i++)cin>>a[i];
    
    dfs(0,0);
    
    for(int i=0;i<N;i++)if(RES[i])ans++;
    
    cout<<ans;
    
    return 0;
}

在这里插入图片描述

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

const int N=1e4;
int a[N];
int ans;
int n,k;

bool isPrime(int n)
{
    for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;
    return true;
}

int main()
{
    cin>>n>>k;

    do{
        int tmpAns=0;
        for(int i=0;i<k;i++)tmpAns+=a[i];
        if(isPrime(tmpAns))ans++;
    }while(next_permutation(a,a+n));
    
    cout<<ans;
    
    return 0;
}

没有过数据，但是好歹样例能过，错误的原因也是如出一辙，都是大量的重复数据！
这里没办法判断重复，因为最好的思路就是转换成字符串进行操作，然后给到SET里面进行判断重复，但是一旦这样做的话，和上面的逻辑一样

在这里插入代码片

在这里插入图片描述

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

const int N=1e4;
int a[N];
int cnt;
int n,k;

bool checkResArr[N];

bool isPrime(int n)
{
    for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;
    return true;
}

int main()
{
    cin>>n>>k;

    do{
        int tmpAns=0;
        for(int i=0;i<k;i++)tmpAns+=a[i];
        if(isPrime(tmpAns))checkResArr[tmpAns]=true;
    }while(next_permutation(a,a+n));
    
    for(int i=0;i<N;i++)if(checkResArr[i])cnt++;
    
    cout<<cnt;
    
    return 0;
}

在这里插入图片描述
即使我加了一部分判断，依然在字符串的情况下难以判重。

4 3 3 7 12 19

第三题滑雪 *

#include<iostream>

using namespace std;

const int N=1e3+10;
int g[N][N];
int dist[N][N];//
int res=0;
int n,m;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};

int dfs(int x,int y)
{
    if(dist[x][y])return dist[x][y];
    
    dist[x][y]=1;
    
    for(int i=0;i<4;i++)
    {
        int tx=dx[i]+x,ty=dy[i]+y;
        //if(g[x][y]>g[tx][ty] && (unsigned int)tx<n&&(unsigned int)ty<m)
        if(g[x][y]>g[tx][ty]&& ((tx-0)|(n-tx-1)|(ty-0)|(m-ty-1))>=0)
            dist[x][y]=max(dist[x][y],dfs(tx,ty)+1);
            
    }
    
    return dist[x][y];
}

int main()
{
    cin>>n>>m;
    
    for(int i=0;i<n;i++)         
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    
    for(int i=0;i<n;i++)         
        for(int j=0;j<m;j++)
            res=max(res,dfs(i,j));            
    dfs(0,0);
    
    cout<<res;
    
    return 0;
}

在这里插入图片描述

第二部分分治法

第一题烦恼的高考志愿

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e6+10;
int a[N],b[N];
int ans ;

int binnarySearch(int x,int l,int r)
{
    while(l<=r)
    {
        int mid = l+r>>1;
        if(a[mid]<x)l=mid+1;
        else r=mid-1;
    }
    return l;
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)cin>>a[i];
    
    sort(a+1,a+n+1);
    //for(int i=0;i<n;i++)cout<<a[i]<<" ";
    //cout<<endl;
    
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
        int idx = binnarySearch(b[i],0,m-1);
        cout<<a[idx]<<" ";
        ans += abs(b[i]-a[idx]);
    }
    cout<<ans;
    return 0;
}

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e6+10;
int a[N],b[N];
int ans ;

int binnarySearch(int x,int l,int r)
{
    int mid = l+r>>1;
    if(l>r || a[mid]==x)return l;
    
    if(a[mid]<x)binnarySearch(x,mid+1,r);
    else binnarySearch(x,l,mid-1);
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)cin>>a[i];
    
    sort(a+1,a+n+1);
    //for(int i=0;i<n;i++)cout<<a[i]<<" ";
    //cout<<endl;
    
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
        int idx = binnarySearch(b[i],0,m-1);
        //cout<<a[idx]<<" ";
        ans += abs(b[i]-a[idx]);
    }
    cout<<ans;
    return 0;
}

第二题平面上的最接近点对

#include<bits/stdc++.h>
#include<cmath>

using namespace std;

const int N=1e5;
int x[N],y[N];

int main()
{
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    
    double res=1e9;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int dx= (y[i]-y[j])*(y[i]-y[j]);
            int dy= (x[i]-x[j])*(x[i]-x[j]);
            res=min(res,sqrt(dx+dy));
        }
    }
    
    cout<<fixed<<setprecision(4)<<res;	
    
    return 0;
}

在这里插入图片描述

第三题砍树 *

木材总长度达到了2E9 ，所以用 long long int

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e6+10;

typedef long long int LL;
LL h[N];
int n,m;

LL check(int Num)
{
    LL sum=0;
    for(int i=0;i<n;i++)if(h[i]>Num)sum+=(h[i]-Num);
    
    return sum;
}

int binnarySearch(int l,int r,int keyN)
{
    int i=l,j=r;
    while(i<=j)
    {
        int mid = (i+j)>>1;
        if((check(mid))<keyN)j=mid-1;
        else i=mid+1;
    }
    
    return i-1;
}

int main()
{
    cin>>n>>m;
    
    for(int i=0;i<n;i++)cin>>h[i];
    sort(h,h+n);

    int r = h[n-1];
    cout << binnarySearch(0,r,m);

    return 0;
}

在这里插入图片描述

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e6+10;
int h[N];
int n,m;

int check(int Num)
{
    int sum=0;
    for(int i=0;i<n;i++)if(h[i]>Num)sum+=(h[i]-Num);
    
    return sum;
}

int binnarySearch(int l,int r,int keyN)
{
    int i=l,j=r;
    while(i<=j)
    {
        int mid = (i+j)>>1;
        if((check(mid))<keyN)j=mid-1;
        else i=mid+1;
    }
    
    return i-1;
}

int main()
{
    cin>>n>>m;
    
    for(int i=0;i<n;i++)cin>>h[i];
    sort(h,h+n);

    int r = h[n-1];
    cout << binnarySearch(0,r,m);

    return 0;
}

在这里插入图片描述

第三部分蛮力法

第一题完美情侣

#include<iostream>

using namespace std;

const int N=1e3+10;
typedef long long int LL;

int a[N],b[N];

int main()
{
    LL n,m,k;
    
    cin>>n>>m>>k;
    
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];

    LL ans=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(a[i]+b[j]==k)ans++;
                    
    cout<<ans;
    
    return 0;
}

在这里插入图片描述

均符合目标输出

第二题化简

#include<iostream>

using namespace std;

const int N=1e6+10;
int a[N];
int cnt;

bool check(int num,int v)//检查最简
{
    for(int i=2;i<=v;i++)if(num%i==0&&v%i==0)return false;
    
    return true;
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=0;i<m;i++)cin>>a[i];
    
    for(int i=0;i<m;i++)
    {
        for(int j=1;j<=n;j++)
            {
                if(j>=a[i]||j>n)break;//把区间定在1-（N-1） 且小于n
                else if(check(a[i],j))cnt++;
            }
        cout<<cnt<<endl;
        cnt=0;
    }       
    return 0;
}

符合样例
在这里插入图片描述

第三题四方定理*

#include<iostream>

using namespace std;

const int N=32768;
bool st[N+10];

int main()
{
    int t,n;
    cin>>t;
    
    for(int i=0;i*i<=N;i++)if(!st[i*i])st[i*i]=true;
    while(t--)
    {
        int cnt=0;
        cin>>n;
        
        for(int a=0;a*a<n;a++)
            for(int b=0;b*b+a*a<n;b++)
                for(int c=0;c*c+b*b+a*a<n;c++)  
                    {
                        int d = n-a*a-b*b-c*c;
                        if(!st[d])continue;
                        if(a*a<=b*b&&a*a<=c*c&&c*c<=d)
                            if(b*b<=c*c&&b*b<=d)
                                if(c*c<=d)
                                    cnt++;
                    }
        cout<<cnt<<endl;            
    }
    
    return 0;
}

在这里插入图片描述

第四部分回溯法

第一题单词方阵

八方向DFS 这已经不能算在考回溯了
这道题的思路我一开始就飞了

我以为是任意情况下的点，开始能不能凑成“yizhong”这个连续字符串，
所依在这种思考背景下，我进入了误区，直接以（0，0）为起始点，走到右下最终点，过程中dfs八个偏移量判断是否符合条件。
同时输入时检查所有数列，将非“yizhong”的字符清空为“*”，在后续的dfs中直接返回，做一个合理性支剪。

后来我发现两个最大的误区，也是这个题目最重要的部分
1.我们不用从左上到右下，因为字符串永远是y开头，我们只要从y开始判定即可
2.符合的要求只需要是八个方向上的直线，不可能出现曲折的线条

依据第二条和第一条，我们就可以发现我们只用判定以Y为中心(n-1)X(n-1)的范围上是不是有满足条件的直线即可

现在我们依据这个思路列出可能的示意图
这是以(2,2)为Y点的示意图，我们可以观察中心点与八条线上的点的关系
在这里插入图片描述
为了理清位置和偏移量的关系我重置了位置图，并画了偏移量的表

即八条直线上的所有位置都可以通过原坐标点以及偏移量来表示
这个时候我们引入stdStr 即题目中要求比对的字符串 “yizhong”的概念，
如果我们的第U个字符串是对应的第U个stdStr字符的话就继续比对，如果一条线上的n-1个都是，即2完成比对

那么我们怎么完成八个方向上的n-1个字符比对呢？
首先我们线比对偏移量为(-1,1)即左上的位置
我们设定

	1.偏移量（-1,1）是所有偏移量中的第P个，只要我们使用(x+dx[p],y+dy[p])即可表示
	2.我们要比对的字符是总数n-1个字符中的第q个，只要我们使用q就可以表示当前第是第几个，而q在完整的过程当中是循环自增到n-1为止的

这样一来我们可以列出检查偏移量（-1,1）时是否满足条件的情况
在这里插入图片描述
那么如何检查八个方向呢？
我们只要再控制一个变量，将方向转移八次，然后重复检查单次的操作即可

我写的代码为了方便，并没有使用递归

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;
char g[N][N];//地图
bool backMap[N][N];//备份地图

int dx[] = { -1,0,1,1,1,0,-1,-1 };
int dy[] = { 1,1,1,0,-1,-1,-1,0 };

string stdStr = "yizhong";
int n;

void dfs(int x, int y)
{
	for (int i = 0; i < 8; i++)
	{
		bool checkWay = true;
		for (int j = 1; j < 7; j++)
		{
			int tx = x + dx[i] * j, ty = y + dy[i] * j;//利用乘j来计算相应坐标
			if((unsigned int)tx<n&&(unsigned int) ty<n) ;else {checkWay = false;continue;}//检查边界
			if (g[tx][ty] != stdStr[j]){checkWay = false;break;}//如果不符合目标StdStr 检查下一个方向
		}
		if (!checkWay)continue;

		for (int j = 0; j < 7; j++)//赋值
		{
			int tx = x + dx[i] * j, ty = y + dy[i] * j;
			backMap[tx][ty] = true;
		}
	}
	return;
}
int main()
{
	cin >> n;

	memset(g, '*', sizeof g);//初始化

	for (int i = 0; i < n; i++)cin >> g[i];//string方式读入
    
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (g[i][j] == 'y')
				dfs(i, j);//找到Y点然后开始搜索6X6的范围，是否存在符合条件

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			if (backMap[i][j])//如果满足条件就输出对应字符
				cout << g[i][j];
			else cout << '*';
		cout << endl;
	}

	return 0;
}

在这里插入图片描述

第二题小偷问题

更新
之前理解错了题目的思路，以为是强制从左往右
如果是随便在中间插入的话，背包思路似乎不使用，我们直接暴力

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e9+10;
const int MaxArrSpace = 1010;

typedef long long LL;

int a[MaxArrSpace];
int minn=N;
int n;

void dfs(int u,int sum)
{
    if(u==n)return ;
    dfs(u+1,sum+a[u]);
    cout<<sum+a[u]<<" ";
    minn=min(minn,sum+a[u]);
}

int main()
{
    cin>>n;
    
    for(int i=0;i<n;i++)cin>>a[i];
    
    for(int i=0;i<n;i++){dfs(i,0);cout<<endl;}
    
    cout<<minn;
    
    return 0;
}

很明白的思路
一个小偷从N个数列当中获取值，但是必须从左往右固定顺序
精简一下，就是一个数值序列，从左往右，获取任意长度下的最小和

我们可以使用NXN暴力比对，当然这里我们使用递归也差不多，N个数字，也就是可能存在的和的数字数量实际不定，我们对N个数字都递归,直到获取到第N个数字位置，过程比对

更新
之前理解错了题目的思路，以为是强制从左往右
如果是随便在中间插入的话，背包思路似乎不使用，我们直接暴力

#include<iostream>
#include<algorithm>

using namespace std;
const int N=1e9+10;
const int MaxArrSpace = 1010;//数组空间

typedef long long LL;

int a[MaxArrSpace];
int minn=N;//最小值
int n;

void dfs(int u,int sum)//u 当前选择的第几个，sum是总和
{
    if(u==n)return ;
    dfs(u+1,sum+a[u]);//递归到下一个
    minn=min(minn,sum+a[u]);//更新
}

int main()
{
    cin>>n;
    
    for(int i=0;i<n;i++)cin>>a[i];
    
    for(int i=0;i<n;i++)dfs(i,0);
    
    cout<<minn;
    
    return 0;
}

但这里出现一个问题
如果所有的值都是正整数

如果我们将
    cout<<sum+a[u]<<" ";
    minn=min(minn,sum+a[u]);
改为
    cout<<sum<<" ";
    minn=min(minn,sum);

左侧是cout<<sum+a[u]<<" “; minn=min(minn,sum+a[u]);
右侧是cout<<sum<<” "; minn=min(minn,sum);
我们可以发现，针对右侧我们是少一个值的，而剩下的一个值又因为sum初始值是0的原因，造成了最小值在全是正数的情况下是0
在这里插入图片描述

那么，为什么在很多非纯正数的数据是正常的呢？
因为一但数值存在负数，那么数值最小值肯定是负数，不可能是0
右侧是

cout<<sum+a[u]<<" ";
minn=min(minn,sum+a[u]);

左侧的是

cout<<sum<<" ";
minn=min(minn,sum);

我们可以很清晰的发现两者的区别
在这里插入图片描述
那么事实上这里的问题出现在哪里呢？
逻辑代码

测试数据

我们检查这里会发现，事实上，我们先递归到了最高层得到sum -2，-2事实上是N个数字相加所得的结果
他是怎么出来的呢？
程序从0递归到最高层n-1，退出,此时开始回溯，将得到的答案输出,但这个时候，我们的回溯到底检查，发现第一层是单纯的sum=0,即sum得初始值，检查所有的值，发现都是从a[0]到a[n-1]累加，当前得a[u]却并没有获取！
我们可以直接观察数值
在这里插入图片描述

推测问题在这一行

dfs(u+1,sum+a[u]);

u+1,但是sum的a[u]却实际是前一个u的值，并没有即时更新
如果我们不更新n个值，而是n+1个值，我们就会发现a[n-1],即第n个值的出现
如果这样写的话，我们要排除的问题就是第一个值是废的
在这里插入图片描述
但我们不能盲目的增设初始值

一旦这样更改就会出现累加错误的情况
即给了初始值之后，下一次执行累加由增加了初始值a[0],a[0]被累加了两次

或者，我们换一个写法
这次我们在递归之前直接更新，输出
很清楚明了的发现，此时的第一次的sum其实是没有任何其他值，只有自身的初始值
在这里插入图片描述
要更改的方式也相同
即增添当前需要的a[u]

所以现在我们总结一下
为什么在很多非纯正数的数据是正常的呢？
因为一但数值存在负数，那么数值最小值肯定是负数，不可能是0
那么事实上这里的问题出现在哪里呢？

dfs(u+1,sum+a[u]);

u+1,但是sum的a[u]却实际是前一个u的值，并没有即时更新
如果我们不更新n个值，而是n+1个值，我们就会发现a[n-1],即第n个值的出现

第三题小猫爬山*

这道题比较好玩

我们要放猫，要自己开新的车

第一步在查找的时候，事实上你时没有车的
这个时候你只能考虑开一辆新车来放🐱

而第二次抱猫，这个时候你就需要思考了，我们唯一拥有的车子是否有剩余的空间？
我们是该放入车里，还是新开一个车来?

每次抱一只新的猫的时候，你都需要从0到当前所有车辆的车子中考虑一遍

以下是 u为当前选择的猫来考虑摆放在哪一个车上的思路
在这里插入图片描述
我们来优化整个过程

这是整个优化的思路

那么，我们可以直接使用贪心吗？
我编写了一个简单的贪心的思路，检查车有没有空余，如果当前的猫能放我就放入，不能的话就开新车

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;
int n,w;
int a[N],sum[N];
int cnt;

bool check(int weight)//检查猫能不能放入车内
{
    for(int i=1;i<=cnt;i++)
        if(weight+sum[i]<=w){sum[i]+=weight;return true;}//能放入，退出
    
    return false;
}

int main()
{
    cin>>n>>w;//n 数量 w 每辆车的最大容量
    
    for(int i=0;i<n;i++)cin>>a[i];//读入数据
    
    sort(a,a+n,[](int a,int b){return a>b;});//反序排序
    
    sum[++cnt]=a[0];//初始化第一辆车
    
    for(int i=1;i<n;i++)if(!check(a[i]))sum[++cnt]=a[i];//如果容量不够放入，我们就需要初始化一辆新的车
    
    for(int i=1;i<n;i++)cout<<sum[i]<<" ";//写出每辆车的现存载重
    
    cout<<endl;
    
    cout<<cnt;//输出车的数量
    
    return 0;
}

数据读出
在这里插入图片描述
我们过掉了样例，那我们成功了吗？
没有
在maxV=16时，重量为9 5 5 5 4 3 的情况下进行测试
贪心结果是9+5 5+5+4 3，结果为3 与我代码的逻辑吻合
但正确结果为9+4+3 5+5+5，结果为2 实际的数量却实际更小
因此我们不能直接盲目使用贪心

在实际的数据当中我们也遇到了相同的问题
在这里插入图片描述
于是我们可以发现，贪心的逻辑在这里是不可行的
我们可以使用DFS暴力搜索每一种方案,即🐱可以放置在现有的🚗中的任意一辆车上,例如

这里我们输出了所有方案的数量，我们会发现在我们的贪心方法错误的数据当中，我们更新到了最优的答案

那么，为什么数据会逐渐变小呢?

	if(cnt>=res)return ;
    if(u>n-1){res=cnt;return ;}
在这两行代码中
	第二行代码，我们选择完了之后进行更新答案
	第一行代码，我们检查当前答案是否大于历史最优值，如果大于，就不继续检查，而是直接返回

正确代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=18+2;
int a[N],sum[N];//a 小猫重量 sum 车现载重
int n,w;
int res;

void dfs(int u,int cnt)//u 当前第几只猫，cnt当前车的数量
{
    if(cnt>=res)return ;//如果车的数量大于现实存在的猫咪的个数，或者历史最优的数值，返回
    if(u>n-1){res=cnt;return ;}//如果考虑完了n只即所有猫咪，则更新答案
    
    for(int i=0;i<cnt;i++)
        if(sum[i]+a[u]<=w)//检查现有的所有车的重量，是否能放猫
            {
                sum[i]+=a[u];
                dfs(u+1,cnt);
                sum[i]-=a[u];
            }
    
    sum[cnt]=a[u];//新增一辆车，初始重量是当前猫的重量
    dfs(u+1,cnt+1);
    sum[cnt]=0;
}

int main()
{
    cin>>n>>w;
    
    res = n;
    
    for(int i=0;i<n;i++)cin>>a[i];
    
    sort(a,a+n,[](int a,int b){return a>b;});//反序排序 优化了搜索顺序 lambda表达式

    dfs(0,0);

    cout<<res;
    
    return 0;
}

反序排序优化，优化了就是20MS，如果未优化则是90MS
在这里插入图片描述
具体数值

第五部分贪心法

第一题陶陶摘苹果（升级版）

思路
首先我们来理解题目的参数

	1.参数n 代表一共有N个数据需要输入
	2.参数a 代表我们可以达到的高度+a
	3.参数b 代表我们起始高度为b
	4.参数s 代表我们一共有s的被减值
	5.参数x 代表每个苹果被摘掉各自需要的高度
	6.参数y 代表每个苹果被摘掉各自需要的力气

现在我们理解整个逻辑：
画一个图给大家看
在这里插入图片描述

从这张图我们可以了解到
	1.a+b 等于我们可以摘取的范围 height
	2.只要有苹果的高度低于 height 就是我们可以摘取的
	3.在所有我们可以摘取的苹果中，我们要摘取最多的数量，我们肯定就要考虑当前耗费力气最小的苹果
	4.一旦我们一直查找最小的苹果知道我们的力气不足以摘取任何苹果，我们就得到了最佳答案

我们依照以上的逻辑编写代码
在这里插入图片描述

现在我们依照这个逻辑来编写代码

AC代码

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

#define x first
#define y second
const int N=5e3+10;
typedef pair<int,int> PII;//定义一个 PII类型 同时拥有 x y  两个数据
PII BeginArr_PII[N];//定义 PII 类型的数组 用来获取初始化数据
vector<PII>TmpArr_PII;//定义PII的不定长数组 用来进行主要的计算
int res; //答案变量

int main()
{
    int n,s,a,b;
    cin>>n>>s>>a>>b;
    int TaoHeight = a+b;//淘淘实际能获取苹果的高度
    
    for(int i=0;i<n;i++)cin>>BeginArr_PII[i].x>>BeginArr_PII[i].y;//获取初始值

    //for(int i=0;i<n;i++)cout<<BeginArr_PII[i].x<<" "<<BeginArr_PII[i].y<<endl;//给出初始值状况 x长度 y力气
    cout<<endl;
    
    for(int i=0;i<n;i++)if(BeginArr_PII[i].x<=TaoHeight)TmpArr_PII.push_back(BeginArr_PII[i]);//将所有初始数据中高度小于height的都放入不定长数组中
    
    sort(TmpArr_PII.begin(),TmpArr_PII.end(),[&](PII a,PII b){return a.y<b.y;});//所有可获得的苹果都按照耗费力气从小到大排序
    
    //for(PII i:TmpArr_PII)cout<<i.x<<" "<<i.y<<endl;//输出排序后的状况
    
    for(PII i:TmpArr_PII)if(s>=i.y)s-=i.y,res++;//只要有力气摘苹果就从小到大的耗费进行摘取，答案自增
    
    cout<<res;//返回答案
    
    return 0;
}

在这里插入图片描述

但这样的代码看起来稍微有些长，我们有没有办法进行优化呢？
整理逻辑

	1.初始化数据
	2.把所有高度小于height的数据丢入新数组
	3.对新数组排序
	4.贪心累加

但细想可以发现，我们没有必要对一定高度放入，可以直接把原有数据排序，省去步骤二，只要我们自定义排序规则时添加条件即可
更新后的AC代码

#include<iostream>
#include<algorithm>
#include<vector>
    
using namespace std;
    
#define x first
#define y second
const int N=5e3+10;
typedef pair<int,int> PII;
vector<PII>TmpArr_PII;
int res;
    
int main()
{
    int n,s,a,b;
    cin>>n>>s>>a>>b;
    int TaoHeight = a+b;
    for(int i=0;i<n;i++){int x,y;cin>>x>>y;TmpArr_PII.push_back({x,y});}
    
    sort(TmpArr_PII.begin(),TmpArr_PII.end(),[&](PII a,PII b){return a.y<b.y;});
        
    for(PII i:TmpArr_PII)if(s>=i.y&&i.x<=TaoHeight)s-=i.y,res++;
        
    cout<<res;
        
    return 0;
}

在这里插入图片描述
我们成功压缩了一半的代码量并且快了4MS

然后是，抄作业的同志，这个做法我写完之后去题解看了一圈都没有这么做的
所以抄的时候不要直接抄这个，因为没人这么写
除了我

方法2
现在我们来考虑更容易理解的方法

我们采用桶排序的方式来规避多一个点同时具有力气高度两个参数的情况

#include<iostream>

using namespace std;

int n,s,a,b;
const int N=100+10;
const int y_len=100;
int arr[N];

int main()
{
    cin>>n>>s>>a>>b;
    const int height=a+b;//小红能达到的长度
    
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        
        if(x<=height)arr[y]++;//以y作为下标 如果这个苹果的高度小于可以达到的 我们就表示 目标力气的苹果+1
    }
    
    
    int res=0;
    for(int i=0;i<=y_len;i++)
        if(s>=i)
            while(arr[i]--)
                if(s>=i)s-=i,res++;//这里的while持续自减是为了避免 我们一次减少多个数字把自己更新为了负数的情况
        else break;//
        
    cout<<res;
    
    return 0;
}

第二题铺地毯

我们理解一下这道题

	1.参数n 总共有N个地毯
	2.参数a b 表示以(a,b)为起点
	3.参数g k 表示以(a,b)为起点，(a+g)X(b+k)的范围被新的地毯覆盖

我们需要理解到，不论前面的地毯姿势多么奇异，只要后面的地毯覆盖到了点(x,y)那么我们就得返回后面地毯的坐标

这种方式下，我们只需要从后往前推范围即可，从第n到第1个地毯，如果被覆盖就直接返回答案

那么，怎么判断点(x,y)是否被覆盖呢？
首先我刚开始的时候直接想错了，我想给一个BOOL的二维数组，然后(a+g)X(b+k)直接覆盖，然后检查是否覆盖了(x,y)点

但事实上，我们可以直接依靠a b g k四个点的数据来判断
即：(x in (range of a,a+g) && y in(range of b,b+k))
那么我们就可以判断点(x,y)在目标范围内，逆序检查的情况下直接返回

#include<iostream>

using namespace std;
const int N=1e4+10;
int n;
int a[N],b[N],g[N],k[N];

int main()
{
    cin>>n;
    
    for(int i=0;i<n;i++)cin>>a[i]>>b[i]>>g[i]>>k[i];//读入数据
    
    int x,y;x=y=0;
    int res=-1;//默认返回-1
    for(int i=n-1;i>=0;i--)
    {
        cin>>x>>y;//读入目标点
        if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i]){res=i+1;break;}//判定范围
    }
    cout<<res;//返回答案
    
    return 0;
}

在这里插入图片描述

第三题局域网*

最小生成树得模板题变形
科里斯卡尔和普里姆都可以解决

解释之后再更新，因为有点多

prim

1.把所有距离初始化为正无穷
2.找到集合外距离最近的点t，在联通块中的点
3.用t来更新其他点到集合的距离
4.把t加到集合中去

1.初始化正无穷
在这里插入图片描述
2.因为集合没有任何点，我们随便找一个点接入集合

3.用t 更新其他点到集合的距离
即其他点到t的距离，否则就继续是INF

4.t 放入集合我们已经使其变绿放入

第二次迭代
2.选中剩下距离到集合最近的点
3.用t 更新其他点到集合的距离
但这里，我们的各个点的最近距离更新之后也并没发生变化
4.t 放入集合我们已经使其变绿放入
在这里插入图片描述

第三次迭代
这里更新比较之后也没有产生变化
在这里插入图片描述
第四次迭代

最小生成树是什么意思呢？
可以理解为我们每一次把新的点接入集合的过程中，存在的对于集合的边的最短的那一个

如图
点1到点2 距离为1的边
点3到点1 或者点2 距离为2的边（因为有两个边可以选择，我们取最小）
点4到点1 距离为3的边

在这里插入图片描述

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int  N = 500+10;//N的点的数量
const int INF=0x3f3f3f3f;//设置一个初始最大值

int g[N][N];//一个稠密图 g[i][j] 从i到j的距离
int dist[N];//用来存储各个点距离集合的距离
bool st[N];//用来判断各个点是否在集合之内
int n,m;

int prim()//prim算法
{
    memset(dist,0x3f,sizeof dist);
    
    int res=0;
    for(int i=0;i<n;i++)//n次迭代
    {
        int t=-1;//标记为一次迭代中，所有剩余的在集合外的点中距离集合最近的距离
        for(int j=1;j<=n;j++)//寻找剩余的点中 距离离集合最近的点
            if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;//如果这个点在集合外 且 是第一个或者距离比当此寻找的t更小 那么就把t更新
        
        if(i&&dist[t]==INF)return INF;//如果不是第一次迭代，那么说明dist t 起码应该是有值对的，如果最小值都是INF，说明不连通
        
        if(i)res+=dist[t];//如果不是第一次迭代，最小生成树添加该边的距离
        st[t]=true;//当前这个点 t(剩余的点中距离集合最短的点) 被纳入集合
        
        for(int i=1;i<=n;i++)dist[i]=min(dist[i],g[t][i]);//使用t来更新其他点到集合的距离
//t是 当次遍历中（也就是剩下未进入集合的点中）距离集合距离最短的 新的 点
    }       
    return res;//返回最小生成树的总长
}

int main()
{
    memset(g,0x3f,sizeof g);//给两个图赋无穷大
    
    cin>>n>>m;
    
    int sum=0;
    
    int u,v,w;
    while(m--)
    {
        cin>>u>>v>>w;
        g[u][v] = g[v][u] = min(g[u][v],w);//无向图的特征 从u到u 从u到v 都是一个距离，且有可能重边，所有取自身和W最小
        sum+=g[u][v];
    }
    
    int t = prim();
    
    
    cout<<sum-t;//总数减去树的长度
    return 0;
}

在这里插入图片描述

第六部分动态规划

第一题采药

我们先进行盲目的贪心方式

这里我们直接计算单价最高，然后按照单价降序排序，每次都获得单价最高

#include<iostream>
#include<vector>
#include<algorithm>

#define x first 
#define y second

using namespace std;
const int N=1e3+10;

typedef pair<int,int> PII;
vector<PII> arr;

int main()
{
    int t,m;
    cin>>t>>m;
    
    int tx,ty;
    for(int i=1;i<=m;i++){cin>>tx>>ty;arr.push_back({tx,ty});}
    
    sort(arr.begin(),arr.end(),[](PII a,PII b){return a.y/a.x>b.y/b.x;});//相当于结构体排序，排序规则是按照单价最高从大到小
    
    int res=0;
    for(PII N:arr)if(t>=N.x)res+=N.y,t-=N.x;
    
    cout<<res;
    
    return 0;
}

检测数据
在这里插入图片描述
这里我们看起来是对了，但究其根本，我们完全不清除这样的贪心是否是正确的决策

继续通过更多的数据
在这里插入图片描述
我们会发现，所有的测试点都出问题了，可见我们的策略是有错误的

我们进行第二种方法

从N个物品里面选择K个物品，并且有着条件限制且只能拿一次，是非常明显的01背包问题
我们复习一次，01背包问题的思考方式
即：
1.正常存储我们所需要读入的数据
2.确定我们的状态表示
3.确定我们的限制条件
4.确定我们的状态转移方程
5.输出答案

以这道题为例，我们首先开始明确参数：

1.T     则表明我们一共有T的时间
2.M     这表明我们一共有M的草药
3.TIME  这表明我们每颗草药分别需要消耗TIME[i] 的时间
4.VALUE 这表明我们每颗草药分别可以获得VALUE[i]的价值

我们思考每个可能存在的状态时，可以表达为
arr[i][j] 即该状态表明，
参数i->现在我们开始判定第i个草药是否需要摘取
参数j->现在我们一共还剩下j的时间可以采药
f[i][j]->表明这个状态下我们一共有 f[i][j]的价值

集合
所以我们相当于一直在考虑不同时间长度不同选择草药的方案的集合（考虑了前i个物品重量为j 的方案的集合）

状态转移方程
我们每次摘取，都要考虑摘取这一次是否能使得我们获得的价值更高
即我们是否该选择第i个

获取答案
我们可以检查在不同背包的容量情况下，我们的价值最高的是哪一个

以下是我们整个的逻辑过程
在这里插入图片描述

#include<iostream>

using namespace std;
const int N=1e3+10;
int arr[N][N*10];
int Time[N],value[N];

int main()
{
    int t,m;
    cin>>t>>m;
    
    for(int i=1;i<=m;i++)cin>>Time[i]>>value[i];//读取数据
    
    for(int i=1;i<=m;i++)    //状态表示
        for(int j=1;j<=t;j++)
            if(j>=Time[i])arr[i][j]=max(arr[i-1][j],arr[i-1][j-Time[i]]+value[i]);//如果剩余有时间，我们就摘取
            else arr[i][j]=arr[i-1][j];//否则就不摘
    
    int res=-1;    
    for(int i=1;i<=t;i++)res=max(res,arr[m][i]);//找到不同剩余时间下的最大价值
    cout<<res;
    
    return 0;
}

在这里插入图片描述
空间优化

#include<iostream>

using namespace std;
const int N=1e3+10;
int arr[N*10];
int Time[N],value[N];

int main()
{
    int t,m;
    cin>>t>>m;
    
    for(int i=1;i<=m;i++)cin>>Time[i]>>value[i];
    
    for(int i=1;i<=m;i++)    
        for(int j=t;j>=Time[i];j--)
            arr[j]=max(arr[j],arr[j-Time[i]]+value[i]);//我们可以依照上面的逻辑直接把二维优化成一维
    
    cout<<arr[t];//因为优化成了一维，所有数据只有不变和变大，我们直接输出最终值即可
    
    return 0;
}

在这里插入图片描述

第二次优化空间

#include<iostream>

using namespace std;
const int N=1e4+10;
int arr[N];

int main()
{
    int t,m;
    cin>>t>>m;
    
    int Time,value;
    for(int i=1;i<=m;i++)
    {
        cin>>Time>>value;
        for(int j=t;j>=Time;j--)
            arr[j]=max(arr[j],arr[j-Time]+value);//直接把F降维成一维，Time,Value省去存储空间
    }

    cout<<arr[t];
    
    return 0;
}

在这里插入图片描述

我们这个时候可以发现的问题在于
DP的概念和记忆化搜索很相似

第二题货币系统

要解决这道题我们需要在01背包问题的基础上拓展完全背包问题
区别在于完全背包问题的是无限可取的，而01背包问题的状态只有取和不取

我们首先复习一下完全背包问题
在这里插入图片描述
完全背包问题思考逻辑

整体逻辑

#include<iostream>

using namespace std;
const int N=1e3+10;
int f[N][N];//状态表示 f[i][j] 表明 前i个物品 体积为j 价值为f[i][j]
int v[N],w[N];//v 重量 w价值

int main()
{
    int n,m;//n数量 m背包容量
    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=0;j<=m;j++)//为什么从0为起始 因为重量可以表示从0到m
            for(int k=0;k*v[i]<=j;k++)//选择第i个物品的数量，只要不超出总容量，显然你就可以一直存放
                f[i][j]=max(f[i-1][j],f[i][j-k*v[i]]+k*w[i]);//当我们抉择第i个是否选择时，这里对比的是可以选择多少第i个物品，或者不选择，使得自身保持不变
    
    int res=0;
    for(int i=1;i<=m;i++)res=max(res,f[n][i]);//在各个选择完数量 但是重量不一致的方案中 挑去价值最高的
    cout<<res;
    return 0;
}

优化
我们这里需要使用三重循环，复杂度显然太高

我们阐明挑选有多少个第i个物品时，f[i][j]的表示

f[i][j]   =max(f[i-1][j],f[i-1][j-v]+w,	f[i-1][j-2*v]+2*w,	f[i-1][j-3*v]+3*w,...)
f[i][j-v] =max(          f[i-1][j-v],	f[i-1][j-2*v]+w,	f[i-1][j-3*v]+2*w,	f[i-1][j-4*v]+3*w,...)
通过观察，我们可以得到 f[i][j]=f[i][j-v]+w;

于是我们可以得到新的状态转移方程

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
        	if(j>=v[i])
           		f[i][j]=max(f[i-1][j],f[i][j-v[i]]);
           	else f[i][j]=f[i-1][j];

我们提交之后发现这样的逻辑是可行的

在这里插入图片描述

现在我们优化空间
降低不必要的空间复杂度

这里降低的依据只有一条就是等价代换

#include<iostream>

using namespace std;
const int N=1e3+10;
int v[N],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];
    
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)//f[i]条件提到循环中 这种情况下更新就只剩一个
            f[j]=max(f[j],f[j-v[i]]+w[i]);//降维
            
    cout<<f[m];//一维只有不增，和增，输出最后一个
    
    return 0;
}

我们再次提交，返现可行
在这里插入图片描述
有了完全背包问题的概念之后，我们来查看问题货币系统

这里值得注意的是，我们求得是方案数量，而非最大价值
我们现在朴素思路走一遍

#include<iostream>

using namespace std;
const int N=3e3+10;
typedef long long LL;//存在爆栈 所以我们使用 long long int 
LL f[N][N];//DP
LL v[N];//货币面值

int main()
{
    int n,m;
    cin>>n>>m;//n钟货币，m的面值
    
    f[0][0]=1;//初始化起点的种数为1
    
    for(int i=1;i<=n;i++)cin>>v[i];//输入不同的面值
    
    for(int i=1;i<=n;i++)//考虑前i种
        for(int j=0;j<=m;j++)//总的面值为j
            for(int k=0;k<=j;k++)//每次取k张面值为v[i]的货币
                if(k*v[i]<=j)//如果我们能拿得下
                    f[i][j]+=f[i-1][j-k*v[i]];//前i种货币且总面值为j的方案数量 累加了 前一种货币时候的所有可能的面值的情况
    
    cout<<f[n][m];//输出数量为n位置为m的方案的数量
    
    return 0;
}

依照这个逻辑，我们发现
当前的状态都是由之前的状态所决定的
我们由第一题的解答所获得的收获可以产生一个疑惑
是不是
1.当前状态由之前的状态所决定
2.拥有记忆化特性
3.拥有搜索特征
的策略即为DP？

现在我们来查看这个方式所耗费的时间
在这里插入图片描述

我们现在利用刚才推导出来的优化空间的版本进行解决

#include<iostream>

using namespace std;
const int N=3e3+10;
typedef long long int LL;
LL v[N];
LL f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)cin>>v[i];
    
    f[0]=1;//初始化为1
    
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
            f[j]+=f[j-v[i]];//直接增加
            
    cout<<f[m];
    
    return 0;
}

在这里插入图片描述

我们继续优化一个空间 v

#include<iostream>

using namespace std;
const int N=3e3+10;
typedef long long int LL;
LL f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    f[0]=1;//初始化为1
    
    int v;
    for(int i=1;i<=n;i++)
    {
        cin>>v;//因为每次都是v[i]，我们直接去掉整个v数组，加入临时变量
        for(int j=v;j<=m;j++)
            f[j]+=f[j-v];
    }
    
    cout<<f[m];
    
    return 0;
}

在这里插入图片描述

现在的时间就被压缩到了11MS

第三题庆功会*

处理这个问题之前，我们先了解一下多重背包问题
在这里插入图片描述

你可以把它理解为01背包问题或者完全背包问题的变体
唯一的区别就是在两者基础上加入了一个东西能放多少个，所以我要加入一个循环

#include<iostream>

using namespace std;

const int N=1e2+10;
int f[N][N];
int v[N],w[N],s[N];

int main()
{
    int n,m;
    cin>>n>>m;
        
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];//s 一个物品最多能获取多少个
    
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k*v[i]<=j&&k<=s[i];k++)//我们挑取K个第i个物品，且总重量不能大于s[i]
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);//我们挑取K个第i个物品，可以挑选多少个


    
    int res=1;
    for(int i=0;i<=m;i++)res=max(res,f[n][i]);//在同样挑选完毕 但是重量不同的方案中得到最佳答案
    cout<<res;
    
    return 0;
}

在这里插入图片描述

优化
优化逻辑参照我前两题写的

Q：为什么这里的注意点1 需要从大到小循环？
A：因为我们压缩的了代码，将二维降低到了一维，f[i, j] = max(f[i - 1, j], f[i - 1, j - v] + w，那么只能从大到小循环，否则计算j时，j - v会先被计算，那么其实算的就是f[i, j] = max(f[i - 1, j], f[i], j - v] + w了，不等价。

#include<iostream>

using namespace std;

const int N=1e2+10;
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    int v,w,s;
    for(int i=1;i<=n;i++)
    {
        cin>>v>>w>>s;
        for(int j=m;j>=0;j--)//注意点1
            for(int k=0;k*v<=j&&k<=s;k++) 
                f[j]=max(f[j],f[j-k*v]+k*w);
    }


    
    cout<<f[m];
    
    return 0;
}

在这里插入图片描述

现在我们来查看庆功会这道题
在这里插入图片描述
很明显是多重背包的裸题

我们直接利用上面优化出来的方式解决这道题目

#include<iostream>

using namespace std;

const int N = 6e3+10;
int f[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    int v,w,s;
    for(int i=0;i<n;i++)
        {
            cin>>v>>w>>s;
            for(int j=m;j>=0;j--)
                for(int k=0;k*v<=j&&k<=s;k++)
                    f[j]=max(f[j],f[j-k*v]+k*w);
        }
    
    cout<<f[m];
    
    return 0;
}

在这里插入图片描述

总结

我希望对本次的所有题目做一个总结
现在我们们列出所有题目的以及对应的题型

	题目									具体题型				具体做法
第一部分 递归
	第一题 数的计算						动态规划				利用数据的规律推导出后面的数据
	第二题 选数							深度优先搜索			n个数据当中选择K个数据，使用DFS暴力搜索
	第三题 滑雪 *							深度优先搜索 && 回溯	使用DFS的同时，检查当前的高度是不是一定大于后面的
第二部分 分治法
	第一题 烦恼的高考志愿					二分					通过二分找出与实际成绩差值的最小值，累加
	第二题 平面上的最接近点对				图论||暴力+勾股定理	通过勾股定理计算出距离
	第三题 砍树 *							二分					通过二分找出找出适合的机器的高度，以最高树的一半2
第三部分 蛮力法
	第一题 完美情侣						暴力					暴力比对数据，if a+b=c then ans++
	第二题 化简							暴力					检查是否是素数
	第三题 四方定理*						暴力					提前用数组判定平方数，然后再用三重循环卡常
第四部分 回溯法
	第一题 单词方阵						深度优先搜索			使用八个方向进行搜索
	第二题 小偷问题						回溯					回溯顺序检查
	第三题 小猫爬山*						深度优先搜索 			重要的是何时生成新的车
第五部分 贪心法
	第一题 陶陶摘苹果（升级版）		 		排序					利用贪心原则，有限摘取符合高度要求的最小值
	第二题 铺地毯							模拟					确定范围，反序查询
	第三题 局域网*						最小生成树			prim或者克洛斯卡尔算法，找到总长减去最小生成树
第六部分 动态规划
	第一题 采药							01背包问题			裸题，确认f[i][j]整体关系
	第二题 货币系统						完全背包问题	 		裸题，加一重循环，找出f[i][j]和f[i][j-v]+w的关系
	第三题 庆功会*						多重背包问题			裸题，加一重关系，确认其与完全背包和多重背包的关系

我们会发现，题目实际上的难度并不高，但是广度却涉猎相对较广,且需要细加分析。
我暂时针对做题总结以下三点：
1.出现了非常多的DFS题目，DFS的方式和生成概念基础且重要，因为递归和回溯还有DFS再很多很多算法都涉及，过于重要了，所以我个人需要好好掌握。
2.很多题目的题型相同，但具体的实现方式和解决的问题都大不相同，这事实上是一个需要自己逐渐熟悉的过程，这里要表明的态度是，我们很需要用简单的方法做，再优化到其他写法，一步到位对我个人是空中楼阁，美好却危险又不可取。
3.很多题目的题型不相同，广度相对较广，但是用法都非常基础，但事实上我们需要知道对应做题的普遍思路和模板，比方说二分,N取K类型的DFS,涉及图的DFS，GCD，欧拉筛，最小生成树，背包问题，他们在这里的应用都有普遍的特征不难，但是需要掌握相关的知识，空想的结果很可能就是只过了样例，或者被迫抄袭，所以我们可能需要见多识广。

猜你喜欢

彻底理解数据库事物
mpvue
Cocos2d-x场景生命周期函数介绍
华为WLAN AC控制器WEB页面射频调优
: 有几个软件包无法下载，要不运行 apt-get update 或者加上 --fix-missing 的选项再试试？
快速建站的php开源程序
FastAdmin CMS 插件下载
Xceed Workbooks|Words for NET -Crack
IGBT窄脉冲现象
交换、路由、路由表
测试技术体系
使用 JSONModel
【Pytorch with fastai】第 7 章：训练SOTA的模型
【收藏】k8s使用securityContext和sysctl
【学习总结】网络-TCP拥塞控制

相关主题

KMP算法详解
算法-贪心算法
JAVA经典算法40例
算法 - KMP算法
A*算法详解
算法-递归算法

zl程序教程

当前栏目

[算法课]实验课全题目详解

文章目录

第一部分递归

第一题数的计算

第二题选数

第三题滑雪 *

第二部分分治法

第一题烦恼的高考志愿

第二题平面上的最接近点对

第三题砍树 *

第三部分蛮力法

第一题完美情侣

第二题化简

第三题四方定理*

第四部分回溯法

第一题单词方阵

第二题小偷问题

第三题小猫爬山*

第五部分贪心法

第一题陶陶摘苹果（升级版）

第二题铺地毯

第三题局域网*

第六部分动态规划

第一题采药

第二题货币系统

第三题庆功会*

总结

相关文章

当前栏目

[算法课]实验课全题目详解

文章目录

第一部分 递归

第一题 数的计算

第二题 选数

第三题 滑雪 *

第二部分 分治法

第一题 烦恼的高考志愿

第二题 平面上的最接近点对

第三题 砍树 *

第三部分 蛮力法

第一题 完美情侣

第二题 化简

第三题 四方定理*

第四部分 回溯法

第一题 单词方阵

第二题 小偷问题

第三题 小猫爬山*

第五部分 贪心法

第一题 陶陶摘苹果（升级版）

第二题 铺地毯

第三题 局域网*

第六部分 动态规划

第一题 采药

第二题 货币系统

第三题 庆功会*

总结

相关文章

第一部分递归

第一题数的计算

第二题选数

第三题滑雪 *

第二部分分治法

第一题烦恼的高考志愿

第二题平面上的最接近点对

第三题砍树 *

第三部分蛮力法

第一题完美情侣

第二题化简

第三题四方定理*

第四部分回溯法

第一题单词方阵

第二题小偷问题

第三题小猫爬山*

第五部分贪心法

第一题陶陶摘苹果（升级版）

第二题铺地毯

第三题局域网*

第六部分动态规划

第一题采药

第二题货币系统

第三题庆功会*