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 ...
一周排行
  • 新作《ASP.NET MVC 5框架揭秘》正式出版
    ASP.NET MVC是一个建立在ASP.NET平台上基于MVC模式的Web开发框架,它提 ...
  • 原文链接:http://www.whitecell.org/forums/viewthread.php?tid=1256 制作人:EBA9A81EE54F32A4B090993B24E140B8 黑客,英文hacke
  • Servlet的學習之Request請求對象(2)
    在上一篇<Servlet的学习(十)>中介绍了HttpServletReque ...
  • 看了一下,大多是些个人电脑使用和优化的贴子,我来发一个服务器优化管理的吧.转载自我的BLOG. Nginx因为它小巧,占用资源少,非常适合Web站点,越来越多的Linux+Nginx+php+MySQL的站点.在近年
  • 


    		    轉 Apache文檔rotatelogs滾動日志
    提到了awstats来分析日志,那么有关apache日志的知识是必须要了解的.现在我就将a
  • 在做全自洽计算时,打开选项       LVTOT = T It is recommended to avoid wrap around errors, when evaluating LOCPOT. This ca
  • 1.从app跳转到Safari 1 NSString* strIdentifier = @"http://www.ybyb.com"; 2 BOOL isExsit = [[UIApplicati ...
  • 1380 没有上司的舞会   时间限制: 1 s 空间限制: 128 KB 题目等级 : 钻石 Diamond       题目描述 Description       Ural大学有N个职员,编号为1~N.他们有从
  • https://oj.leetcode.com/problems/sqrtx/ 求一个数的开方,二分查找一个数,直到这个数的平方 - target 小于 0.001. 但这道题出的不好,返回值竟然是 int ,脑洞太 ...
  • #include<stdio.h> int main(void) { int x,y; scanf("%d",&x); if(x<1){ y=x; } else if(x ...