题解 | #方块与收纳盒#

链接：https://ac.nowcoder.com/acm/contest/24213/1001 来源：牛客网

题目描述 现在有一个大小n1的收纳盒，我们手里有无数个大小为11和2*1的小方块，我们需要用这些方块填满收纳盒，请问我们有多少种不同的方法填满这个收纳盒

输入描述: 第一行是样例数T 第2到2+T-1行每行有一个整数n（n<=80），描述每个样例中的n。 输出描述: 对于每个样例输出对应的方法数 示例1 输入 复制 3 1 2 4 输出 复制 1 2 5 说明 n=4，有五种方法 1:1 1 1 1 2:2 1 1 3:1 2 1 4:1 1 2 5:2 2 备注: 对于100%的数据， 0 < T < 80; 0 < n <= 80。 从集合角度 **题解：

f[j]表示体积为j的方案总数---以最后一个不同点（选择1还是2）划分集合，由于集合属性为数量（所以要将所有状态相加+） 地f[j]=fj-i **

#include<bits/stdc++.h>
using namespace std;
const int N=100;
typedef long long ll;
ll f[N];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(f,0,sizeof(f));
        int n;
        cin>>n;
        f[1]=1,f[2]=2;
        for(int j=1;j<=n;j++)
        {
            if(j<=2)continue;
            for(int i=1;i<=2;i++)
            {
                if(j>=i)
                f[j]+=f[j-i];
            }
        }
       
      cout<<f[n]<<endl;
    }
    return 0;
}