AcWing 1050. 极简做法：查克拉分配分身=(苹果放置盘子)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1050. 极简做法：查克拉分配分身=(苹果放置盘子) 原题链接中等

作者：

Safe_Sound , 2020-02-17 15:23:38 , 所有人可见 , 阅读 7123

147

55

这道题目相当于是把n个苹果放m个盘子里的一道题.

C++ 代码

#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;

int f(int x,int y){
    if(x == 0) return 1;//没有苹果，全部盘子为0
    if(y == 0) return 0;//没有盘子，没法放
    if(y > x){//盘子数大于苹果数，至多只能x个盘子上都放一个 
        return f(x,x);
    }
    return f(x - y, y) + f(x, y - 1);//盘子数小于等于苹果数 -> 分类讨论： 有盘子为空，没有盘子为空
//有盘子为空的时候即至少有一个盘子为空，f(x,y-1);没有盘子为空即最少每个盘子都有一个,f(x-y,y)     
}

int main(){
    int t,n,m;//n个苹果分到m个盘子里去，运行盘子为空 
    cin >> t;
    while(t --){
        cin >> n >> m;
        cout << f(n,m) << endl;
    }
    return 0;
}

实际上我们可以发现，在递归的过程中就是要用到之前的数据，继而这道题可以转换为记忆化搜索将结果保存来做，即dp做法，但是这个dp是从递归去思考出来的- -而不是像灿总那样直接思考dp做法.

#include<iostream>
#include<cstdio>
using namespace std;
int a[25][25],m,n;
int main()
{
    int t,m,n;
    for(m=0;m<=10;m++)
        {
            for(n=0;n<=10;n++)
            {
                if(m<n)a[m][n]=a[m][m]; 
                else if(m==0)a[m][n]=1;
                else if(n==0)a[m][n]=0;
                else a[m][n]=a[m-n][n]+a[m][n-1];
            }
        }
    scanf("%d",&t);
    for(int i=1;i<=p;i++)
    {
        scanf("%d%d",&m,&n);

        printf("%d\n",a[m][n]);
    }
    return 0;
}

26 评论

面壁者北茶 7个月前

我这个算法貌似也蛮好的哦：

#include <iostream>

using namespace std;

int ans;

// 剩余能量为 rem, 还能制造 cnt 个分身
// 当前方案已经制造的分身中最大消耗 maxv 的能量 
void dfs(int rem, int cnt, int maxv = 0) {
    // 能量恰好全部用于制造分身 
    if (!cnt && !rem) {
        ans++;
        return;
    }

    // 如果能量耗尽或者分身达到最大个数了, 该方案无效 
    if (!cnt && rem || cnt && !rem) {
        return; 
    }

    // 以后制造的分身能量不能低于当前
    for (int i = maxv; i <= rem; i++) {
        dfs(rem - i, cnt - 1, i); 
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--) {
        ans = 0;

        int m, n;
        cin >> m >> n;
        dfs(m, n);

        cout << ans << '\n';
    }

    return 0;
}

Shier833_Ww 2023-03-31 23:22

谢谢楼主的分享，看后思路清晰很多！

但刚刚在写题时，有一点疑惑：为什么要先考虑if(果子==0)的情况,再考虑if(盘子==0)的情况（即为什么a[0][0]=1）呢?

思考后得出如下结论（原因）：是为了保证a[0][n] = a[0][0]时，a[0][n]的值不会错

我的具体分析过程如下（从考虑可能会用到a[0][0]值的两种情况，切入分析）：

情况①: 在”a[m][n]=a[m-n][n]+a[m][n-1]“中用到了a[0][0]
- [前提] 符合 m≥n且m,n≠0
- i. a[m-n][n]=a[0][0] , 即m=n=0 → 不符合m,n≠0的前提,舍去
- ii. a[m][n-1]=a[0][0] , 即m=0且n=1 → 不符合m≥n的前提,舍去

情况②: 在a[m][n]=a[m][m]中用到了a[0][0]
- 【前提】符合 m<n
- 此类仅有当m=0;n=1,2,...,n时符合, 即a[0][n](n>0) = a[0][0]
- 又由于a[0][n](n>0), 属于有盘子, 却没苹果的情况, 此类情况拥有唯一方案:每个盘子均为空 ==> 故a[0][n](n>0) = 1;
- 而代码中 a[0][n] = a[0][0], 因此要把a[0][0]设为1, 才能保证a[0][n]的值不会错.