Description 有n个点，它们从1到n进行标号，第i个点的限制为度数不能超过A[i].
现在对于每个s (1 <= s <= n)，问从这n个点中选出一些点组成大小为s的有标号无根树的方案数。
Data Constraint 20%的数据：n <= 6
60%的数据：n <= 50
100%的数据：n <= 100
Solution 【GDOI|【JZOJ5068】【GDSOI2017第二轮模拟】树】这道题是一道带标号的无根树计数，我们考虑prufer序列。
首先先讲一下prufer序列怎么求：对于一棵树，我们每次删去最大的叶子结点，并输出它的父亲，知道树中只剩下两个点，因为这时我们已经知道整棵树的连边情况，所以就不用删了，整个序列长度为n-2。求出一个prufer序后，我们就可以知道整棵树的连边情况，也就说树唯一确定。
我们设出f[i][j][k]表示前i个点选出j个点，构成的prufer序的长度为k（解释一下为什么会有k这一维：因为一开始有可能是森林，后面才逐渐合并成树）那么我们发现一个度数为a[i]的点最多在prufer中出现a[i]-1次，所以我们转移为f[i][j+1][k+l]+=f[i][j][k](0 <=l< a[i])，f[i][j][k]+=f[i-1][j][k]。复杂度O（n^4）.
Code
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const ll maxn=1e2+5,mo=1004535809;
ll f[maxn][maxn][maxn],a[maxn],c[maxn][maxn];
ll n,i,t,j,k,l,x,y,z;
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%lld",&n);
for (i=1;
i<=n;
i++)
scanf("%lld",&a[i]);
c[0][0]=1;
for (i=1;
i<=n;
i++){
c[i][0]=1;
for (j=1;
j<=n;
j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mo;
}
f[0][0][0]=1;
for (i=1;
i<=n;
i++)
for (j=0;
j<=i;
j++)
for (k=0;
k 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 题解|【HNOI2017】大佬-dalao
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)
- 经典题|3462: DZY Loves Math II
- Android|【常用工具类】DensityUtils（dp px 互相转换）