首页 > ACM题库 > HDU-杭电 > HDU 1436 排列组合(二)-字符串-[解题报告] C++
2013
12-10

HDU 1436 排列组合(二)-字符串-[解题报告] C++

排列组合(二)

问题描述 :

有N个字母,每个字母的数量不定。用这N个字母组成一个长为M的串,并且规定这个串中每个字母能出现的次数。求这样的串的总数。

输入:

每组输入数据的第一行有两个数字N,M。接下来有N行,每行的第一个数k表示对应字母可以出现的种数,接下来的k个数表示该字母可以在串中出现的个数。其中0表示可以不出现。如测试数据,第一个2表示有"A""B"两个字母,第二个2表示求一个长度为2的串,第二行的第一个数3表示后面有3个数字,0,1,2分别表示字母"A"在这个串中可以出现0次,1次,2次,第三行表示字母"B"可以出现的次数。则这样的串有"AB","BA","AA"3种。

输出:

对应每组输入,输出满足要求的串的总数。(输出结果不会超出2^63)

样例输入:

2 2
3 0 1 2
2 0 1

样例输出:

3

题意:

有N个字母,每个字母的数量不定。用这N个字母组成一个长为M的串,并且规定这个串中每个字母能出现的次数。求这样的串的总数。

分析:

之前处理好组合数c[][],然后d[i]表示字符串长度为i的时候用所给字符串构成的满足条件的情况数,

递推式:  d[s[i][k]+j] += d[j]*c[m-j][s[i][k]];

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define clr(x)memset(x,0,sizeof(x))
const int maxn = 1001;
__int64 c[maxn][maxn],d[maxn],s[maxn][maxn];

void cc(__int64 m)
{
    int i,j;
    for (i=1; i<=m; i++)
    {
        c[i][0] = 1;
        for (j=1; j<i; j++)
            c[i][j] = c[i-1][j-1]+c[i-1][j];
        c[i][i] = 1;
    }
}
int main()
{
    int n, m;
    int i, j, k;
    while (scanf("%d %d",&n,&m)!=EOF)
    {
        cc(m);
        for (i=0; i<n; i++)
        {
            scanf("%d",&s[i][0]);
            for (j=1; j<=s[i][0]; j++)
                scanf("%d",&s[i][j]);
        }
        clr(d);
        for (i=1; i<=s[0][0]; i++)
        {
            if (s[0][i] > m)
                continue;
            d[s[0][i]] = c[m][s[0][i]];
        }
        for (i=1; i<n; i++)
        {
            if (!s[i][0])
                continue;
            for (j=m; j>=0 ; j--)
            {
                if (d[j])
                    for (k=1; k<=s[i][0] && j+s[i][k]<=m; k++)
                    {
                        if (s[i][k] > 0)
                            d[s[i][k]+j] += d[j]*c[m-j][s[i][k]];
                    }
            }
        }
        printf("%I64d\n",d[m]);
    }
    return 0;
}

 

解题报告转自:http://www.cnblogs.com/dream-wind/archive/2013/01/29/2881576.html


  1. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?