poj1173 解题报告

http://poj.org/problem?id=1173

发现此题资料甚少,斗胆第一次写一份解题报告
【题意】
    输入 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的向量,例如 1100 -》 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: 1100 8: 1100100
1: 0 9: 1100110
2: 1001 10: 1101
3: 1001100 11: 1101100
4: 1000 12: 1100
5: 1011 13: 0010
6: 1000 14: 0100
7: 0 15: 0110

【代码】

#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/454852/blog/1374384518#!app=2&via=QZ.HashRefresh&pos=1374384518

更多相关文章
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • 一.原题中文大意. 1      2       3      4       5      6         7     8 9     10       11    12      13     14       15    16 17    18      19    20       21 ...
  • //我是莱鸟,多多交流 //380k //94ms 题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大. 解题思路: 准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后 ...
  • Spring1F Dice(HDU 5012)解题报告及测试数据
    Dice Time Limit:1MS     Memory Limit:65536KB Description There are 2 special dices on the table. On each face of the dice, a distinct number was writt ...
一周排行
  • 目录 1.Tengine编译安装 2.FPM制作Tengine为RPM包 3.总结 1.Tengine编译安装 [[email protected] ~]# cat /etc/issue CentOS release 6.4 (Fin ...
  • 迭代期间无变更?支持派说:对,如果经常变,我们怎么开发啊. 反对派说:不对,敏捷开发不能上来就确认了需求,要的就是在开发中逐步了解需求,怎么可能不变呢. 只在开发层面,这个问题无解.让我们站在研发心理学的高度来看这个 ...
  • 前言: 传统的互联网广告一般都是大流量网站在页面中留出一定空位,某些推广商家通过买位的方式来展示自己的广告. 我们这里引入一个案例:假设大访问量网站为博客园,想要广告推广的公司为阿里云平台. (场景为虚构,请勿对号入 ...
  • 


    		    配置windows 2008 作爲遠程訪問SSLVPN伺服器系列之一
    一.新的协议SSTP的支持及介绍 随着windows server 2008的发布,相信新
  • cat -n 命令可以给文件的每行都加上行号 本文出自 "leiothrix相思鸟" 博客,请务必保留此出处http://kevinleo.blog.51cto.com/341461/648772
  • 1.安装soap扩展 2.安装openssL 3.代码执行 function  issure($sn){//通过soap链接接口  进行确认是否是正确的sn码    try{        $client = new
  • 動態合並Repeater控件數據列 Ver2
    前一版本<动态合并Repeater控件数据列>http://www.cnblo ...
  • url中的#! URL 中的 # 本来的用途是跳转到页内锚点.一个 URL 中 # 后的值 (hash tag) 不影响所访问网页的内容,所以搜索引擎在处理仅仅 hash tag 不同的多个 URL 时会当做相同内容
  • 轉載OpenWrt sysupgrade 命令行更新固件到最新版
    OpenWrt sysupgrade 命令行更新固件到最新版 下面我们要使用 sysupg
  • WSAWaitForMultipleEvents函数 熟悉WSAEventSelect模型的朋友对这个函数肯定不会陌生,不对,其实大家都不应该陌生,这个函数与线程中常用的WaitForMultipleObjects函 ...