CCF 100012. 技能树

100012. 技能树

思路:区间dp。

状态:dp[i][j]表示节点为i,高度小于等于j的方案数。

状态转移:dp[i][j]=∑dp[k][j-1]*dp[i-1-k][j-1]。

节点为i,高度等于j的方案数等于dp[i][j]-dp[i][j-1]。

代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pi acos(-1.0)
#define pii pair<int,int>
#define mem(a,b) mam(a,b,sizeof(a)) const int MOD=;
const int N=;
const int M=; int dp[N][M];
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,m;
cin>>n>>m; for(int j=;j<M;j++)dp[][j]=;
for(int i=;i<N;i+=)
{
for(int j=;j<M;j++)
{
for(int k=;k<=i-;k+=)
{
dp[i][j]=(dp[i][j]+dp[k][j-]*dp[i--k][j-])%MOD;
}
}
} cout<<(dp[n][m]-dp[n][m-]+)%MOD<<endl;
return ;
}
上一篇:如何学习一门新技术-iOS开发


下一篇:电梯调度设计之初感想——蔡迎盈&&曹玉松