当智加科技的无人驾驶车队首次进行横跨美洲的生鲜运输时，工程师阳阳注视着一桶桶的黄油陷入了沉思。他突发奇想，要这一切都是标准化包装物件，那么其尺寸不仅节约控件、提升干线物流运输效率，同时也让简化车辆的动力学、运动学建模，帮助自动驾驶算法更精准、灵敏地操控车辆（但愿如此）。
如果现有两种包装物品的包装运输箱，尺寸分别是长宽 1米×1米 和 1米×2米。
假定用这两种箱子排成一片 m列n行 (m米×n米) 的阵列，不限两种箱子的使用数量（注意：1米×2米 箱子不能旋转方向使用，即不能作为 2米×1米 的箱子跨列摆放在阵列中）；
【本题编程】在此基础上，若我们限制箱子阵列必须存在交错排列，以确保货物在运输过程中稳定，则有多少种不同的排列方式？
注意：对于一个 m米×n米 的阵列，交错排列的定义是：不存在行方向上的某一个位置 k米处 (1<k<n) 可以沿着箱子之间的缝隙将阵列完全
分离成 m米×k米 和 m米×(n-k)米 两个阵列。
第一行输入为 整数 m (1<=m<=10)第二行输入为 整数 n (1<=n<=10)
第一行输出为结果整数
2 2
3
m = int(input()) n = int(input()) # 不考虑缝隙的排列方案数 dp = [0] * 11 dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 2] + dp[i - 1] # 考虑缝隙的排列方案数 dp2 = [0] * 11 for i in range(1, n + 1): dp2[i] = dp[i]**m # 先初始化为不考虑缝隙的方案数 # 枚举缝隙，将有缝隙的方案减掉 for j in range(1, i): dp2[i] -= dp2[j] * dp[i - j]**m print(dp2[n])这里解释一下dp2数组，dp2[i]表示将黄油排列成m*i规模的阵列有多少种交错的方案。将其初始化为不考虑存在缝隙的方案数，然后枚举缝隙位置，把有缝隙的方案去掉。
f[0]=f[1]=1; for(i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];
for(i=1;i<=n;i++)
{
dp[i]=1;
for(j=1;j<=m;j++)
dp[i]*=f[i];
} 再加上不存在缝隙这个条件，可以用总方案数-存在缝隙方案数。 #include <bits/stdc++.h>//ASI
typedef long long ll;
using namespace std;
ll n,m,tt,f[105],dp[105],dp2[105],sum=0,a[15];
void dfs(int all,int t)
{
int i;
if(all==tt)
{
ll s=1;
for(i=1;i<t;i++)
s*=dp2[a[i]];
sum+=s;
}
for(i=1;i<tt;i++)
{
if((all+i)>n)
return ;
a[t]=i;
dfs(all+i,t+1);
}
}
int main()
{
int i,j;
cin>>m>>n;
f[0]=f[1]=1;
for(i=2;i<=n;i++)
f[i]=f[i-1]+f[i-2];
for(i=1;i<=n;i++)
{
dp[i]=1;
for(j=1;j<=m;j++)
dp[i]*=f[i];
}
dp2[1]=1;
for(i=2;i<=n;i++)
{
tt=i;
sum=0;
dfs(0,1);
dp2[i]=dp[i]-sum;
}
cout<<dp2[n];
return 0;
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
