问题标题: 酷町堂:酷町堂5071,WA10分,啊啊啊啊啊啊啊啊啊求解!!!!

0
0
刘旭晨
刘旭晨
初级守护
初级守护

My code

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <string>
    #include <cstring>
    #include <map>
    #include <vector>
    #include <queue>
    #include <stack>
    #define MAXN 1000010
    typedef long long ll;
    using namespace std;
    int read()
    {
        int ans = 0;
        char ch = getchar();
        while (!isdigit(ch) && ch != '-') ch = getchar();
        bool sign = false;
        if (ch == '-') sign = true, ch = getchar();
        while (ch >= '0' && ch <= '9') ans = ans * 10 + (ch - '0'), ch = getchar();
        return (sign == true ? -ans : ans);
    }
    #define F(a) for(int i=1;i<=a;i++)
    long long test,a[MAXN];
    long long f(int n,int x)
    {
        if(a[n]) return a[n];
        if(n==1) return 1;
        long long int ans=0;
        for(int i=x;i<=3&&i<=n;i++)
        {
            ans+=f(n-i,i);
        }
        a[n]=ans;
        return ans;
    }

    int main()
    {
        int n;
        n=read();
        cout<<f(n,1);
        return 0;
    }

但是只有十分,请Dalao帮忙康康啊啊啊!


0
汪宇航
汪宇航
新手启示者
新手启示者

what?????????????????????????

0
汪恺恒
汪恺恒
中级启示者
中级启示者

这题不需要读入优化,可以用记忆化搜索

0
0
杜文博
杜文博
资深守护
资深守护

大佬,能把题目发一下吗?

0
李玥仑
李玥仑
中级光能
中级光能

帮你补充一下:

5071   搬箱子

经验值:0 时间限制:1000毫秒

题目描述 Description

现在快递运输需要搬一些箱子,但规定一次最多只能搬三个箱子。那将这些箱子搬走共有多少种不同的搬法。
例如,现在总共有4个箱子,那么可以选择的方法有以下7种:
1,1,1,1(分4次搬完,每次搬一个箱子)
1,2,1(分3次搬完,第一次搬一个,第二次搬两个,第三次搬一个)
1,1,2(分3次搬完,第一次搬一个,第二次搬一个,第三次搬两个)
2,1,1(分3次搬完,第一次搬两个,第二次搬一个,第三次搬一个)
2,2 (分2次搬完,第一次搬两个,第二次搬两个)
1, 3 (分2次搬完,第一次搬一个,第二次搬三个)
3, 1 (分2次搬完,第一次搬三个,第二次搬一个)
共7种;
但对拆分出的数字要求按照字典序排序后,
1,2,1 和1,1,2和2,1,1 都会排成1,1,2 字典序,排序后属于1种方案
1,3和3,1都会排成1,3字典序,排序后属于1种方案
方案不能重复,
所以现在的方案为:
1,1,1,1
1,1,2
1,3
2,2
共4种

对拆分出的数字要求按照字典序排序,方案不能重复,求方案数。

输入描述 Input Description

箱子总数

输出描述 Output Description

对拆分出的数字要求按照字典序排序,方案不能重复,的方案数

样例输入 Sample Input

4

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

n<=50

0
0
我要回答