4514
f[i]表示i个椭圆最多可以把平面分成f[i]个地盘
递推式:f[i]=f[i-1]+2(i-1)(其中i-1表示前i-1个椭圆,2表示第i个椭圆会和每个椭圆相交2次,每相交一次会产生1个新的地盘)*
边界:f[1]=2
解:f[n]
代码:
#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m;
int main(){
cin>>n;
int f[26];
f[1]=2;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+2*(i-1);
}
cout<<f[n];
}
4515
小P最近搬进了新家,打算布置一番。现在小P有n本不同的书,想放进带有m个格子的书架上(m<n)。要求每个格子至少有一本书。请你帮小P计算有多少种布置的方案。
定义:f[i][j]表示前i本书放入j个格子的方案总数,(每个格子至少放1本书)
递推式:f[i][j]=f[i-1][j]*j+f[i-1][j-1]
边界:f[1][1]=1;
解:f[n][m]
代码:
#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m,f[100][100];
int main(){
cin>>n>>m;
f[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(i==1&&j==1) continue;
f[i][j]=f[i-1][j]*j+f[i-1][j-1];
}
}
cout<<f[n][m];
}
课后测: