题解 P1595 【信封问题】

vivarock

2017-12-27 13:23:26

Solution

//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; } //蒟蒻思路,神犇勿喷 ```