题解 P1595 【信封问题】
vivarock
2017-12-27 13:23:26
//oier蒟蒻汗水结晶
主要思路:
用f【i】表示i个数的错排;
第一步:考虑放第n个元素,有n-1种;
第二步:考虑第k个元素,如果第n放在了位置k,则还有f【i-1】种。否则还有f【i-2】种;
递推公式:f【i】=(i-1)\*(f【i-1】+f【i-2】);
递推边界:f【0】=0;f【1】=0;f【2】=1;
```cpp
#include<bits/stdc++.h>//万能头文件
#define For(i,j,n) for(int i=j;i<=n;++i) //宏定义,很好用
using namespace std;
int a[25];//递推数组
int main(){//主函数
ios::sync_with_stdio;//让cin和scanf一样快
int n;
cin>>n;//读入
a[0]=0;a[1]=0;a[2]=1;//递推边界
For(i,3,n)a[i]=(i-1)*(a[i-1]+a[i-2]);//递推过程,可能有点难理解,自己用草稿纸按我思路来推一下,就知道了
cout<<a[n];//输出
return 0;
}
//蒟蒻思路,神犇勿喷
```