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

输出格式：

你的程序应完成任务：
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);
    }
} 

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

一、问题描述

“条形码”是一种由亮条（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{枚举当前的大写字母

}