365bet亚洲版登录-bet官网365入口

365bet亚洲版登录拥有超过百间客房,bet官网365入口的文化历经几十年的传承和积淀形成的核心内容获得业界广泛的认可,365bet亚洲版登录是目前信誉最高的娱乐场所,同国内外几百家网上内容供应商建立了合作关系。

子序列的个数

子种类的个数

标题详细情况: 子连串的概念:对于三个队列a=a[1],a[2],......a[n],则非空种类a'=a[p1],a[p2]......a[pm]为a的二个子连串,当中1<=p1<p2<.....<pm<=n。

举例:4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子种类。 对于给出系列a,有个别子系列大概是一律的,这里只算做1个,必要输出a的分歧子系列的数量。

输入: 长度为n的数组1<=n<=100,数组成分0<=a[i]<=110

出口:子体系的个数对一千000007取余数的结果(由于答案比非常的大,输出Mod 一千000007的结果即可)。

函数底部: C/C++: int run(cons int *a,int n); java public static int run;

  那道难点也是干扰了自家相当久,一贯找不到相比好的不二等秘书籍,那道问题应该是足以用动态规划做出来的,因而笔者也特意去学习动态规划的沉思,并找了一部分操演题做,可是那么些意况转移方程着实难住自个儿了,本来数学基础日常般,那就更大了难度。即便笔者最后化解了那道标题,不过那是确立在大神指导的情况下做出来的,小编在此间只是把题解写出来,顺便裨补阙漏,看看自身的明白是或不是精确,其实,想和做是四回事,这里也请大家给予指正。

题解:

  假若子体系的前k个数的子种类个数为d,那么**前k

  • 1个头体系的个数就为d个子连串,从k - 1k**的变通是哪些的吧?

  1、如果数组a[N]k个数为a[k],如果a[k] 与日前的k - 1个数都不相同,那么就有 : d = d + 【**d + 1】 =**2d + 1,为啥呢?能够这么想,对于前k- 1项的子种类个数为d,那前k个数,无非就是在前k - 1项的底蕴上多加了二个数a[k](a[k]与前k - 1个数轻松一个都十分),那就在原本的咬合上助长a[k],就有d个,还应该有八个a[k]协和组合四个子类别,所以还要加1;

  2、假设a[k] 与前方的k - 1个数里面二个等于,那依旧丰盛前k - 1个子类别个数d,不过出于前面有与a[k]也正是的数,所以要减小重复的片段,怎样找到重复的一部分吗,假诺离k近来的一个与a[k]相当于的数为第t个a[t] = a[k],即序列(a[1], a[2], ……,a[t],……,a[k - 1],a[k]),a[t] = a[k];大家早已掌握连串(a[1], a[2], ……,a[t])的队列个数为d,这便是说d正是重复的一对,这里须要和谐做雅观法,也是算法的入眼部分,这里本人要表明的地点是,干什么只须求找到离k近日的t使得a[t] = a[k]?给出的解说是:大家是从1 - n对数组进行遍历的,计算d的i正是从1到n依次总结的,那么第一次遇到a[k] = a[t]的情景满意条件:有且独有四个t使得a[t] = a[k],例如类别(1, 2, 3, 2, 4, 2),分别总结d,d,d,d,d,d;大家在计算d的时候开掘a[4] = a[2],所以d = 2*d - d = 2d;当总括d的时候也会有a[6] = a[4] = a[2],但是由于我们眼下已经把a[2]双重的局地减掉了,所以无需再减,d = 2 * d - d = 2d.

  进程繁琐,我总计一下结论:

  状态转移方程为:

    d = 2 * d + 1; a[k] != a[i],i = 1,2,3……k - 1;

    d = 2 * d - d; 从k往前寻找,存在离k近年来的t,使得a[t] = a[k].

  动静转移方程深入分析出来的话,剩下的为主便是小菜一碟了,代码如下:

图片 1图片 2

/*    以下是题目详情: 子序列的定义:对于一个序列a=a[1],a[2],......a[n],    则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列,其中1<=p1<p2<.....<pm<=n。     例如:4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。 对于给出序列a,有些子序列可能是相同的,    这里只算做1个,要求输出a的不同子序列的数量。 输入: 长度为n的数组1<=n<=100,数组元素0<=a[i]<=110    输出:子序列 的个数对1000000007取余数的结果(由于答案比较大,输出Mod 1000000007的结果即可)。    函数头部: C/C++:   int run(cons int *a,int n); java   public static int run;*/#include <stdio.h>#include <stdlib.h>#define M 1000000007int run(const int *a,int n){    long long SubArray[120] = {0};    int LastIndex[120] = {0};    int iter = 0;    for(iter = 1; iter <= n; iter++)    {        switch(LastIndex[a[iter - 1]])        {        case 0:            {                SubArray[iter] = (2 * SubArray[iter - 1] + 1) % M;                break;            }        default:            {                SubArray[iter] = (2 * SubArray[iter - 1] - SubArray[LastIndex[a[iter - 1]] - 1] + M) % M;                break;            }        }        LastIndex[a[iter - 1]] = iter;    }    return SubArray[n] % M;}int main(void){    //int a[5] = {1, 2, 2, 3 ,3};    int a[4] = {1, 2, 3 , 2};    printf("the result is %dn", run(a, 4));    return 0;}

View Code

本文由365bet亚洲版登录发布于计算机网络,转载请注明出处:子序列的个数

您可能还会对下面的文章感兴趣: