跳至正文

USACO 3.2.2 Stringsobits 解题报告

  • OI路程

这题最开始,我是爆搜,从1向上递增地搜,没过,超时了;后来用深搜,直接搜位数小于等于l的,也超时了,实在没有办法了,到网上看了题解,天!好简单阿! f[i][j]代表i位长的且1最多为j的二进制数的个数,那么就有一个DP方程,f[i][j] = f[i – 1][j] + f[i – 1][j – 1] 因为第i位要么是1要么是0,如果是0那个数就是f[i – 1][l],如果是1就是f[i – 1][j – 1]。 之后,根据f[i][j]就可以确定输出了,从f[n][l]开始,如果m<=f[n – 1][l],那么就0,否则就输出1,且l–, m -= f[n – 1][l] 代码如下: de lang="c"> / LANG: C ID: yylogoo1 PROG: kimbits / #include int f[32][32]; int main(void) { int i, j; int n, l; unsigned m; freopen("kimbits.in", "r", stdin); freopen("kimbits.out", "w", stdout); scanf("%d%d%u", &n, &l, &m); for(i = 0; i 0; i–){ if(m

发表回复

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