poj1173 解题报告

poj1173 解题报告2013-07-21 13:31 by 期待、, 42 阅读, 0 评论, 收藏, 编辑

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

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

输出这种模式的条形码的有多少个？

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

【解题思路】
动态规划+组合数学。
     我们举一个例子：n=7，k=4，m=3。
⑴计算个数
要计算此模式条形码的数量，那么我们只要分别计算出
            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，其余的值都可以通过递推得到

⑵计算序号
首先将长度为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://www.cnblogs.com/hezhichao/p/3203639.html

http://user.qzone.qq.com/454822252/blog/1374384518#!app=2&via=QZ.HashRefresh&pos=1374384518

巴特西

poj1173 解题报告