跳至正文

USACO 2.3.2 Cow Pedigrees 解题报告

这题我折腾了一个星期,真的好死心,一个多星期一直在查到底是哪里出了问题,从感觉上算法是没有错误的,而且能够拿90分,那问题到底出在哪里呢?这一题我反反复复得找,再看标程,对着看,终于昨晚上找到了,算法没有一点问题,实现上有问题,超过了int 的范围,所以数据就出现了错误,然后就OVER了。 题目的思路是这样的,f[i][j]代表i个节点构成j层的树的个数,那么dp方程就是f[i][j] = {2 f[k][j – 1] f[i – k – 1][l]}(l = 1….j – 2, k = 1..i – 2) {f[k][j – 1] f[i – k – 1][l]} (l == j – 1, k = 1…i – 2) 这个算法的优化: 其实不需要从1循环到n,或者什么的,因为树和题目的特殊性质,不需要完全枚举,比如说当i=7的时候就不可能构成一层的树,就没必要考虑,当i=7的时候至少是3层,怎么计算呢?当已知节点数,log2(i) + 1的是最少的层数,(i – 1) / 2 + 1 是最大的层数。 当已知层数i时,最少的节点数是i 2 – 1,每层都有两个,但第一层只有一个;最多为2^i – 1,所以时间的优化还可以。 代码实现如下: de lang="c">/ LANG: C ID: yylogoo1 PROG: nocows / #include

#include #define MOD 9901 int f[200][100]; int table[101][202],N,K,c; int smalltrees[101][202]; int getend(int i) { // return i / 2 + 1; return (i << 1) + 1; } int getstart(int i) { return ((int)log2(i)) + 1; } int main(void) { int i, j, k, l, t; int n, m, lim, lim2; freopen("nocows.in", "r", stdin); freopen("nocows.out", "w", stdout); scanf("%d%d", &n, &m); f[1][1] = 1; for(i = 3; i

发表回复

您的电子邮箱地址不会被公开。