By

 /  ? views

文章目录
  1. 1. 题意
  2. 2. 解题思路
  3. 3. 代码

发现此题资料甚少，斗胆第一次写一份解题报告

题意

输入 n（代表二进制位数） k（代表黑条白条总共有几条，条形码是以黑条开始的，再白黑交替出现） m（代表每条最多占多少个二进制位）
输出这种模式的条形码的有多少个？

输入s，再输入s个二进制形式的条形码
输出每个条形码在该模式中的序号，序号是根据二进制条形码的十进制数值排序，序号从0开始。

解题思路

动态规划+组合数学。

我们举一个例子：n=7，k=4，m=3。

1.计算个数

要计算此模式条形码的数量，那么我们只要分别计算出

n=6，k=3，m=3。
n=5，k=3，m=3。
n=4，k=3，m=3。

再将他们相加即可。

扩展到一般，得公式 [n，k] = ∑[n-i，k-1]（i = 1，2···m-1，m）

根据推算，我们可以将公式化简成 [n,k] = [n-1,k] + [n-1,k-1] - [n-m-1,k-1]

我们令[0,0]=1, 令 [0,1]至[0,k] 和 [1,0]至[k,0] =0，其余的值都可以通过递推得到

2.计算序号

首先将 长度为n的二进制条形码 转换成 长度为k的向量，例如 1101110 -》 2131（2个1，1个0，3个1，1个0）
2131之前的条形码可以分为四部分：

1???    [6,3] = 7
22??    [3,2] = 1
23??    [2,2] = 2
211?    [3,1] = 1
212?    [2,1] = 1

合计为12,对照下面题目给出的表,确是如此 !

至于究竟上面是如何弄出来的，需要分黑条和白条分别考虑，不是很好说明，看代码应该能懂。
还有一点，我们都知道0在二进制位里面越前，1越后，则该数值会越小（即序号越小）。

0: 1000100 | 8: 1100100
1: 1000110 | 9: 1100110
2: 1001000 | 10: 1101000
3: 1001100 | 11: 1101100
4: 1001110 | 12: 1101110
5: 1011000 | 13: 1110010
6: 1011100 | 14: 1110100
7: 1100010 | 15: 1110110

代码

#include <iostream>
using namespace std;

int n,k,m;
int dp[40][40]={0};//下标分别对应着 n+1 和 k+1
int s;
char bin[40];//存储每次输入的二进制串
int vec[40];//将二进制的bin数组 转换成 k部分的向量
int count[102];

void table()//打表 计算还剩 n位 和 k部分时 有多少种情况
{
    dp[0][0]=1;
    for(int j=1;j<=k;j++)//一列列的计算
        for(int i=1;i<=n;i++)
        {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];//等于 左上和上面 这2个之和
            if(i-m-1>=0)
                dp[i][j]-=dp[i-m-1][j-1];
        }
}

void binToVec()//将二进制的bin数组 转换成 k部分的向量 并且保存到vec数组中
{
    int c=0;
    char first;
    for(int i=0,j=0;i<n;i--)
    {
        c=1;
        first=bin[i++];
        while(bin[i++]==first)
        {
            c++;
        }
        vec[j++]=c;
    }
}

int countOrder()//计算该二进制的序号
{
    int count = 0;
    for(int i=0,u=n;i<k-1;i++)
    {
        if(i%2==0)//针对编码为1的部分
        {
            for(int j=1;j<vec[i];j++)
            {
                if(u>=j)
                    count+=dp[u-j][k-i-1];
            }
        }
        else//针对编码为0的部分
        {
            for(int j=m;j>vec[i];j--)
            {
                if(u>=j)
                    count+=dp[u-j][k-i-1];
            }
        }
        u-=vec[i];
    }
    return count;
}

int main()
{
    cin>>n>>k>>m;
    table();
    cin>>s;
    for(int i=0;i<s;i++)
    {
        cin>>bin;
        binToVec();
        count[i] = countOrder();
    }
    cout<<dp[n][k]<<endl;//输出总共有多少种
    for(int i=0;i<s;i++)//输出相应二进制编码的序号
    {
        cout<<count[i]<<endl;
    }
}

　

　

版权声明

本文首发于 贺智超的博客（http://hezhichao.cn/ or http://hzc199307.github.io），转载请注明出处。

本文链接：http://hezhichao.cn/acm/solution_report/poj1173/
永久链接：http://hzc199307.github.io/acm/solution_report/poj1173/

文章目录
  1. 1. 题意
  2. 2. 解题思路
  3. 3. 代码