条形码问题 dp+求某个序列在某种排列中的序号的…

2018-06-17 22:05:52来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目

条形码是一种由亮条(Light Bar)和暗条(Dark Bar)交替出现且以暗条为起头的符号,每条都占有若干个单位宽。图33-1给出了一个含有4个条的条形码,它延续了1+2+3+1=7单位的宽。

 一般情况下BC(N,K,M)是一个包含所有由K个条,总宽度正好为N个单位,每个条的宽度至为M个单位性质的条形码组成的集合。例如:图33-1的条形码属于BC(7,4,3)而不属于 BC(7,4,2)。 图33-2显示了集合BC(7,4,3)中的所有16个符号,其中1表示暗,0表示亮。图中所示条形码已按字典顺序排列,冒号左边数字为条形码的编号。图33-1的条形码在BC(7,4,3)的编号为4。

输入格式:

   输入文件Input4.DAT的第一行为N、K、M的值(1≤N,K,M≤33)。第二行为数字S(0≤S≤100),而后的S行中,每行为一个图33-2那样描述的集合BC(N,K,M)中的一个条形码。

输出格式:

你的程序应完成任务:
A、把输出内容写入文件OUPUT4.DAT。第一行是BC(N,K,M)中条形码的个数。
B、OUPUT.DAT的第二行起的S行中,每一行是输入文件对应条形码的编号;输入与输出数据中同一行相邻两个数之间用空格区分。
 
首先是求出条形码个数。可以很容易地得出状态转移方程:

ans(n,k,m)=sum{ans(n-x,k-1,m)}(1<=x<=min(m,n-k+1),km>=n)(n>k)
ans(k,k,m)=1
ans(t,k,m)=0(t<k)

然后是求每个条形码的序号,这个需要一些技巧。

***记一下

举例:1101000,求序号
l[1]=2,l[2]=1,l[3]=1,l[4]=3
比其小的有:
先是l[1]<2的(ans[7-1][3]=7)
再是l[1]=2,l[2]>1的(ans[7-2-2][2]+ans[7-2-3][2]=2+1=3)
还有l[1]=2,l[2]=1,l[3]<1的(0)
还有l[1]=2,l[2]=1,l[3]=1,l[4]>3的(0)
因此其序号是7+3+0+0-1+1=10
其他的以此类推

***

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int ans[40][40];
int n,m,k,num,temp,temp2;
int l[40];
int s;
string s1;
int ans2;
int dfs(int n,int k)
{
    if(k*m<n)
    {
        ans[n][k]=0;
        return 0;
    }
    if(n>k)
    {
        ans[n][k]=0;
        for(int i=1;i<=min(m,n-k+1);i++)
            if(ans[n-i][k-1]==-1)
                ans[n][k]+=dfs(n-i,k-1);
            else
                ans[n][k]+=ans[n-i][k-1];
    }
    else if(n==k)
        ans[n][k]=1;
    else ans[n][k]=0;
    return ans[n][k];
}
int main()
{
    int i,p,j,j1;
    memset(ans,-1,sizeof(ans));
    scanf("%d%d%d",&n,&k,&m);
    printf("%d\n",dfs(n,k));
    scanf("%d",&s);
    for(i=1;i<=s;i++)
    {
        ans2=0;
        cin>>s1;
        p=0;
        num=0;
        for(j=0;j<s1.length()-1;j++)
        {
            p++;
            if(s1[j]!=s1[j+1])
            {
                l[++num]=p;
                p=0;
            }
        }
        l[++num]=p+1;
        temp=n;
        temp2=k;
        for(j=1;j<=num;j++)
        {
            temp2--;
            if(j%2==1)
                for(j1=1;j1<l[j];j1++)
                {
                    ans2+=ans[temp-j1][temp2];
                }
            else
                for(j1=l[j]+1;temp-j1>=temp2&&j1<=m;j1++)
                {
                    ans2+=ans[temp-j1][temp2];
                }
            temp-=l[j];
        }
        printf("%d\n",ans2);
        //1101110
        //1100
    }
    return 0;
}

再贴一段其他人的代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k,m,s,a[100000];
long long f[1000][1000];
char c[100];
int main(){
    scanf("%d%d%d%d",&n,&k,&m,&s);
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=k;j++)
    for(int l=1;l<=min(m,i);l++)
    f[i][j]=f[i][j]+f[i-l][j-1];
    printf("%d\n",f[n][k]);
    for(int i=1;i<=s;i++){
        scanf("%s",c);c[n]=(c[n-1]-'0')^1+'0';
        int ans=0,sum1=0,sum2=0,num=0,p=1;
        for(int j=1;j<=n;j++)if(c[j]!=c[j-1])a[++num]=p,p=1;else p++;
        for(int j=1;j<=num;j++){
            sum2++;
            if(j&1)for(int l=a[j]-1;l>=1;l--)ans+=f[n-sum1-l][k-sum2];
            else for(int l=a[j]+1;l<=m;l++)ans+=f[n-sum1-l][k-sum2];
            sum1+=a[j];
        }
        printf("%d\n",ans);
    }
} 
View Code

再贴一段讲解,并没有什么卵用:

动态规划和搜索有着千丝万缕的关系,我们先来看一个例子:

一、问题描述

“条形码”是一种由亮条(light bar)和暗条(dark bar)交替出现,且以暗条起头的符号。每个“条”(bar)都是若干个单位宽。图1给出了一个含4个“条”的“条形码”,它延续了1+2+3+1=7个单位宽。

一般情况下,BC(n,k,m)是一个包含所有由:k个“条”,总宽度正好为n个单位,每个“条”的宽度至多为m个单位的性质的“条形码”组成的集合。例如:图1的条形码属于BC(7,4,3),而不属于BC(7,4,2)。

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

图1 图2

图2显示了集合BC(7,4,3)中的所有16个符号。1表示暗,0表示亮。图中的条形码已按字典顺序排列。冒号左边的数字为“条形码”的编号。图1中条形码的在BC(7,4,3)中的编号为4。

输入:输入文件的第一行为数字n,k,m(1<=n,k,m<=30)。第二行为数字s (s<=100)。而后s行中,每行为一个如图1那样描述的集合BC(n,k,m)中的一个“条形码”。

输出:在输出文件中第一行为BC(n.k,m)中“条形码”的个数。而后s行中每一行为输入文件中对应“条形码”的编号。

输入输出示例:

二、分析

题目有两问。容易看出,计数是求序号的基础,因此我们先解决计数问题。原题只给了一个实例,即条形码。为了能用计算机解决该问题,我们必须先建立一个能够很好描述该问题的数学模型。

由于条形码是由黑白相间的且以黑色起头的k块组成,每一块最少含有1条,最多含有m条,k块合起来为n条。因此,一个条形码可以由一个k元组(x1,x2,…,xk)表示,且1≤xi≤m,∑(i=1..k)xi=n。相应地,任意一个满足上述条件的k元组唯一表示一个满足条件的条形码。容易证明,所设的k元组与条形码满足一一对应的关系。满足条件的条形码的个数即为所设的k元组的个数。即方程∑(i=1..k)xi=n,1≤xi≤m的整数解的个数。

最容易想到的是搜索算法1:由于xi的取值范围已经确定,我们可以穷举所有的xi的取值,再检查有多少组解满足∑(i=1..k)xi=n。程序很容易编写,但复杂度却很高,为mk,由于m,k都可能达到30,因此该算法是很低效的。

搜索算法低效的原因是没有很好的利用∑(i=1..k)xi=n这个约束条件,而只将其作为一个判定条件。最容易想到的改进策略是:如要求方程x1+x2+x3=4,1≤x1,x2,x3≤2的整数解的个数。若x1=1,则方程化为x2+x3=4-x1=4-1=3,若x1=2方程化为x2+x3=2。原方程的整数解的个数,正是方程x2+x3=3,x2+x3=2的整数解的个数的和。这样,我们把含3个未知数的方程的整数解个数的问题化为了若干含2个未知数的方程的整数解个数的问题。以此类推,最终可以化为求含一个未知数的方程的整数解个数的问题。容易得出,方程x=n,1≤x≤m的整数解的个数为:当1≤n≤m时,有1个解,否则,有0个解。

容易写出搜索算法2:

Func Count(k,n):LongInt;{∑(i=1..k)xi=n,1≤xi≤m的整数解个数}

begin

if k=1 then if 1≤n≤m then Count:=1

else Count:=0

else for i:=1 to m do Inc(Count,Count(k-1,n-i)){***}

end;

k该程序的时间复杂度仍然为m ,但我们可以通过改进{***}句而将复杂度降低到O(N),

其中N为Count函数的返回值,即方程的整数解个数。具体方法是通过修改循环语句的起始值和终止值:for i:=MinI to MaxI do Inc(Count,Count(k-1,n-i));其中,MinI=Max{1,n-m*(k-1)},MaxI=Min{m,n-k+1}。而方程的整数解个数可以达到6*10甚至更高。显然,这个程序是不高效的。其原因在于所建立的数学模型的抽象程度不高。

我们将方程的整数解个数的模型进一步抽象为:k个在1..m之间的数的和为n的方案数。新的模型与方程的整数解个数的模型似乎没有不同,仅仅是将原模型中未知数xi抽象为k个数。但事实上,这个并不大的变化可以很大程度上的优化程序:我们用F(k,n)表示k个在

1..m之间的数的和为n的方案数,显然有方程式

F(k,n)=∑(i=1..m)F(k-1,n-i)。

和初始条件:若i≠0则F(0,i)=0,F(0,0)=1。

容易写出动态规划程序:

Proc Count;

begin

FillChar (F, Sizeof (F), 0);

F [0,0]: =1;

for i:=1 to n do

for j:=1 to k do

for p:=1 to m do

if i>=p then Inc(F[i,j],F[i-p,j-1])

end;

动态规划的程序的时间复杂度为O(n*k*m)≤30*30*30=27000。

动态规划的特点之一是速度快,另一点便是丰富了运算结果。如本题,我们不仅计算出题设条形码的个数,还计算出了所有由i块组成,每一块最少含有1条,最多含有m条,i块一共为j条的条形码的个数(1≤i≤k,1≤j≤n)。而这些信息可以很方便的解决本题的第二问。

要计算一个条形码的编号,可以先统计在字典顺序中比该条形码小的条形码的个数。这是很容易做到的。具体程序如下:

Func Index (n, k, p: Integer): LongInt;

begin

if k<=1 then Index:=1 else begin

x:=0;

if Odd(p) then begin q:=1;Delta:=1 end else begin q:=m;Delta:=-1 end;

while l[p]<>q do begin

if n>=q then Inc(x,F[n-q,k-1]);

Inc (q,Delta)

end;

8

Inc (x, Index (n-q, k-1, p+1));

Index: =x

end

end;

其中L数组存放的是所读入的条形码的所对应的k元组。如条形码1001110对应的L数组为L[1]=1,L[2]=2,L[3]=3,L[4]=1。该过程的时间复杂度为O(n*k)≤30*30=900

再得到了完美的解答之后,我们再来看看前面的搜索算法。容易看出,搜索算法2可改为:

Func Count(k,n):LongInt;{∑(i=1..k)xi=n,1≤xi≤m的整数解个数}

begin

if F[k,n]=NULL then

if k=0 then F[k,n]:=1

else for i:= Max{1,n-m*(k-1)} to Min{m,n-k+1} do

Inc (F [k, n], Count (k-1, n-i));

Count: =F [k, n]

end;

改进后的算法即为动态规划的递归式写法。此算法可以看作是动态规划算法的改进。因为对决策变量i的初始值和终止值的修正,使得其计算次数较递推写法的动态规划更少。也就是说,我们通过对搜索的算法的改进,得到了同样的动态规划的算法。

那么动态规划与搜索的关系究竟是什么呢,我们再来看另外一个问题:

序关系计数问题 (福建试题)

一、问题描述

用关系‘<’和‘=’将3个数A、B和C依次排列有13种不同的关系:

A<B<C, A<B=C, A<C<B, A=B<C, A=B=C, A=C<B,

B<A<C, B<A=C, B<C<A, B=C<A,

C<A<B, C<A=B, C<B<A。

编程求出N个数依序排列时有多少种关系。

二、分析

<1>.枚举出所有的序关系表达式

我们可以采用回溯法枚举出所有的序关系表达式。N个数的序关系表达式,是通过N个大写字母和连接各字母的N-1个关系符号构成。依次枚举每个位置上的大写字母和关系符号,直到确定一个序关系表达式为止。

由于类似于‘A=B’和‘B=A’的序关系表达式是等价的,为此,规定等号前面的大写字母在ASCII表中的序号,必须比等号后面的字母序号小。基于这个思想,我们很容易写出解这道题目的回溯算法。

算法1,计算N个数的序关系数。

procedure Count(Step,First,Can);

{Step表示当前确定第Step个大写字母;

First表示当前大写字母可能取到的最小值;

Can是一个集合,集合中的元素是还可以使用的大写字母}

begin

if Step=N then begin{确定最后一个字母}

for i:=First to N do if i in Can then Inc(Total);{Total为统计的结果}

Exit

end;

for i:=First to N do{枚举当前的大写字母}

if i in Can then begin{i可以使用}

Count(Step+1,i+1,Can-[i]);{添等号}

Count(Step+1,1,Can-[i]){添小于号}

end

end;

调用Count(1,1,[1..N])后,Total的值就是结果。该算法的时间复杂度是O(N!)

图4-8 N=3时的解答树

<2>.粗略利用信息,优化算法1

算法1中存在大量冗余运算。如图4-8,三个方框内子树的形态是完全一样的。一旦我们知道了其中某一个方框内所产生的序关系数,就可以利用这个信息,直接得到另两个方框内将要产生的序关系数。

显然,在枚举的过程中,若已经确定了前k个数,并且下一个关系符号是小于号,这时所能产生的序关系数就是剩下的N-k个数所能产生的序关系数。

设i个数共有F[i]种不同的序关系,那么,由上面的讨论可知,在算法1中,调用一次Count(Step+1,1,Can-[i])之后,Total的增量应该是F[N-Step]。这个值可以在第一次调用Count(Step+1,1,Can-[i])时求出。而一旦知道了F[N-Step]的值,就可以用Total:=Total+F[N-Step] 代替调用Count(Step+1,1,Can-[i])。这样,我们可以得到改进后的算法1-2。

算法2,计算N个数的序关系数。

procedure Count(Step,First,Can);

{Step,First,Can的含义同算法1}

begin

if Step=N then begin{确定最后一个字母}

for i:=First to N do if i in Can then Inc(Total);{Total为统计的结果}

Exit

end;

for i:=First to N do{枚举当前的大写字母

}

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:#106. 二逼平衡树(附带详细代码注释)

下一篇:atoi(),itoa() ,atol(),atof ()的实现