题解 P1595 【信封问题】

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;

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