有一些装有铀 U和铅 L的盒子,数量均足够多。要求把 n n n ( n ≤ 30 ) (n \le 30) (n≤30) 个盒子放成一行,但至少有 3 3 3 个装有 U 的盒子放在一起,有多少种放法?
这道题是紫书上很典的一道递推,因为
n
≤
30
n \le 30
n≤30 所以并不会爆 int ,我们设
f
i
f_i
fi 为前
i
i
i 个盒子的总方案数,那么就有:
f
0
=
f
1
=
f
2
=
0
,
f
3
=
1
,
f
4
=
3
f_0=f_1=f_2=0,f_3=1,f_4=3
f0=f1=f2=0,f3=1,f4=3
第
n
n
n 位的答案即为
f
n
f_n
fn 。好的,前置条件有了,我们来推导一下递推式。这里我们需分类讨论:
现在已经有
3
3
3 个装有 U 的盒子放在一起,满足条件,那么当前第
i
i
i 个盒子则有两种选择,分别为放 U 和放 L ,再根据乘法原理得出
f
i
=
2
⋅
f
i
−
1
f_i=2 \cdot f_{i-1}
fi=2⋅fi−1
当前并不满足条件,想要合法,那么前面的盒子里放的元素一定为 LUU ,我们就需要求前面的盒子不合法的方案数,就用全部的方案数减去合法的方案数就是不合法的方案数。我们得出方案数为
2
i
−
4
−
f
i
−
4
2^{i-4} - f_{i-4}
2i−4−fi−4
那么,递推式就为:
f
i
=
2
⋅
f
i
−
1
+
2
i
−
4
−
f
i
−
4
f_i=2 \cdot f_{i-1}+2^{i-4} - f_{i-4}
fi=2⋅fi−1+2i−4−fi−4
我们就可以用递推式与前置条件将从 5 5 5 到 n n n 的方案数推出来,最后输出即可,时间复杂度为 O ( n ) O(n) O(n) 。
Code
#include <bits/stdc++.h>
#define int long long
#define AC return 0
#define M(a) memset(a,0,sizeof a)
#define il inline
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int N=100010;
int f[N];
int n;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
f[3]=1;
f[4]=3;
while(cin>>n && n) {
rep(i,5,n) f[i]=pow(2,i-4)-f[i-4]+2*f[i-1];
cout<<f[n]<<endl;
}
AC;
}
这次我们用 f i f_i fi 来表示前 i i i 个盒子的不合法总数。
我们知道总方案数为
2
n
2^n
2n ,那么答案就为
2
n
−
f
n
2^n - f_n
2n−fn
我们来讨论一下不合法方案数:
Code
#include <bits/stdc++.h>
#define int long long
#define AC return 0
#define M(a) memset(a,0,sizeof a)
#define il inline
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int N=100010;
int f[N];
int n;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(cin>>n && n) {
M(f);
f[1]=2; f[2]=4 ;f[3]=7;
rep(i,4,n) f[i]=f[i-1]+f[i-2]+f[i-3];
int Ans=pow(2,n)-f[n];
cout<<Ans<<endl;
}
AC;
}
T h e e n d The \; end Theend