UVA - 580 Critical Mass 四种方法（dp/暴力）
题目链接
吐槽：组合数学的方法是最难想的（对本题而言）
dp
方法一
这种是比较容易想到的DP，求安全系数。设 f [ i ] [ 0 / 1 / 2 ] f[i][0/1/2] f[i][0/1/2]分别表示当前第 i i i位以 L ; U ; U U L;U;UU L;U;UU结尾的个数，显然当要出现三个 U U U时立刻截断，则：
int solve1(int n){
f[1][0]=f[1][1]=1;
f[1][2]=0;
for(int i=2;i<=30;i++){
f[i][0]=f[i-1][0]+f[i-1][1]+f[i-1][2];
f[i][1]=f[i-1][0];
f[i][2]=f[i-1][1];
}
return (1<<n)-f[n][0]-f[n][1]-f[n][2];
}
方法二
若考虑直接求危险系数，那么设 d [ i ] d[i] d[i]为长度为 i i i的危险个数，显然有两种情况：
- 若前面已经满足出现三个 U U U，则当前需要累加 d [ i − 1 ] ∗ 2 d[i-1]*2 d[i−1]∗2
- 若前面的不满足，因为不满足的情况比较难求，我们考虑求前面的总个数减去安全组合数，因为如果前面的不满足，现在的最后四个必须是 L U U U LUUU LUUU，前 i − 4 i-4 i−4个的总个数为 2 i − 4 2^{i-4} 2i−4，减去的个数应该是长度为 i − 4 i-4 i−4的满足的个数（这个已经求出）
int solve2(int n){
d[3]=1,d[4]=3;
for(int i=5;i<=30;i++)
d[i]=d[i-1]*2+(1<<i-4)-d[i-4];
return d[n];
}
方法三
这个暂时没有看懂
int solve3(int n){
d[1]=2,d[2]=4,d[3]=7;
for(int i=4;i<=30;i++){
d[i]=d[i-1]+d[i-2]+d[i-3];
}
return (1<<n)-d[n];
}
暴力搜索
最大为30，显然可以爆搜，如果害怕超时可以打表提交：
void dfs(int cur){
if(cur==n+1){
ans++;
//for(int i=1;i<=n;i++) cout<<d[i]; cout<<endl;
return;
}
if(cur>=3){
for(int i=1;i>=0;i--){
if(i==1 && d[cur-1]==1 && d[cur-2]==1){
d[cur]=0;
dfs(cur+1);
break;
}
d[cur]=i;
dfs(cur+1);
}
}else{
for(int i=0;i<2;i++){
d[cur]=i;
dfs(cur+1);
}
}
}