首页 > 代码库 > 动态规划解不包含相同数字的子串个数问题

动态规划解不包含相同数字的子串个数问题

2024-08-08 08:45:21   222人阅读

比赛描述

    仙灵女巫露露，对于魔法的热忱可是超出常人，要是发现了什么上古遗留下的魔法，她总是想方设法地获得，然后研究分析。而最近，他又从邪恶小法师维嘉那里获得了一个“奇怪”的魔法卷轴；

    这个魔法卷轴上有一大串数字，而且根据卷轴上的描述，这个魔法的威力指数来自于这一串数字中“魔法区间”的数量；

    所谓“魔法区间”指的是一段连续的闭区间，且这段区间上的所有数字均不相同；

    现在，露露想知道这个魔法的威力指数，你能帮帮她么？



输入

先输入一个正整数T，表示样例个数，1≤T≤10。

对于每一个样例，先输入一个正整数n，表示卷轴上的数字个数(1≤n≤106)；

再输入n个整数，第i个数ai，表示卷轴上第i个数（0≤ai≤106）。

输出

对于每个样例，输出一个正整数，即威力指数。

题目保证结果在int范围内。

样例输入

1
3
1 2 3

样例输出

6

提示

  1. 读入数据请使用 scanf()；

  2. 对于样例，共有{1},{2},{3},{1,2},{2,3},{1,2,3}，6个魔法区间，所以威力为6。


思路：

        这道题数据范围是1000000，理论上允许的最大时间复杂度为nlog(n)以下，首先考虑用动态规划求解。
        动态规划的目标即为找到状态转移方程，假设一共n个数字在数组num[n]中，其中包含前i个数字的解 为answer[i], 那么我们就是要找到状态转移方程T，使
                                                         answer[i+1]=T(answer[i])             （1）
        那么answer[i+1]和answer[i+1]存在怎样的关系呢？

       明显的，前i+1个数字所创造的“魔法空间”肯定是包含了前i个数字创造的“魔法空间”的，并且多出了一部分包含第i个数字的魔法空间。也就是说，（1）式可
进一步写成：
                                                         answer[i+1]=answer[i]+F(i+1)       (2)
        其中F(i+1)为包含第i+1个数字的魔法空间数量。
        
        所以这道题的目标进一步转化成：当我们有i+1个数字时，包含第i+1个数字的魔法空间有多少？

        当然， 我们可以从i+1个数开始回溯，一个一个把数字添加到空集中，直到集合无法保持没有重复数字，那么这个集合的长度就是包含第i+1个数字的序列数（所有序列都依次为后缀子序列）。
        以长度为4的序列 1 2 3 1 为例
        当包含3个数字时， 含有的魔法空间数为6.即 1， 2， 3， 12，23，123 。
        当加入第四个数字后，又增加了231，31，1 （不同于第一个1）, 所以1 2 3 1 的魔法空间数为9 。

优化

        求F的过程，可以尽量采取一些聪明的做法。 不断地添加数字并每一次检查序列是否合法是不明智的。
        当我们从第i个数字向前回溯时，显然到一个位置j,且num[j]==num[i]时必须停止，因为集合已经重复了。 那么我们从i+1回溯时，也不可能超过j这个位置。（因为依然包含了num[i]这个数，它与num[j]是重复的）。 我们设第i个数的前一个相同值数字所在位置为mark[i].所以在每一次回溯时，我们可以设定一个值limit(初始为0),表示我们可以达到的最前方的位置。然后在回溯的过程中，对于每一个k(k<i+1), 我们更新limit  if (mark[k]>limit) . 因为我们不可能超过mark[k]这个位置。
         那么回溯将在以下条件结束：
                  达到limit 或者num[k]==num[i+1].
        回溯的距离也就是F（i+1）。 从而我们得到了完整的状态转移方程。

       由以上思路完成的代码如下：
     
#include<iostream>
#include<algorithm>
using namespace std;
int f(int n)
{
    return (n+1)*n/2;
}
int num[1000000];
int mark[1000000];
int main()
{
    int i,j,n,T;
    scanf("%d",&T);
    //cin>>T;
    while(T--)
    {
        cin>>n;
        memset(mark,0,sizeof(mark));
        for(i=0;i<n;i++)
        {
            scanf("%d",&num[i]);
        //    cin>>num[i];
        }
        int sum=0;
        for(i=0;i<n;i++)
        {
            int temp=0;
            int limit=0;
            for(j=i-1;j>=limit;j--)
            {
                if(num[j]==num[i])
                    break;
                temp++;
                if(mark[j]>limit)
                    limit=mark[j];
            }
            mark[i]=j+1;
        //    cout<<i<<" "<<temp+1<<endl;
            sum+=temp+1;
        }
    //    cout<<"limit:";
    //    for(i=0;i<n;i++)
    //        cout<<mark[i]<<" ";
     //   cout<<endl;
        cout<<sum<<endl;
    }
}


进一步优化

           不幸的是，以上算法在南邮acm系统上发生了TLE （TIME LIMIT EXCEED）。
          回顾我们的做法和我们的初衷， 会发现如果我们面临的是n个完全不同的数字，那么每次在第i个位置回溯的距离都将是i， 算法的时间复杂度为可怕的On2 .

          看看我们哪里犯傻了呢？

          犯傻的地方就是上一段中的黑体字：
         当我们从第i个数字向前回溯时，显然到一个位置j,且num[j]==num[i]时必须停止，因为集合已经重复了。 那么我们从i+1回溯时，也不可能超过j这个位置。
         

          这个做法并非smart,实际上，我们应该保存的不应该是每一个数字前一个数字的位置，尽管这样可以帮助我们减少回溯的距离，不过仔细想想，在第i+1个位置能回溯的距离，不是仅仅和第i个位置能回溯的距离有关吗？

           我们来整理一下思路，假设我们之前有i个数字，并且已经得到了一个解（动态规划的立足点），那么当加入第i+1个数字时，得到的解可以通过求F（i+1）(包含第i+1个数字的区间数)来得到， 而 这个区间数其实就是包含第i+1个数字的最长的魔法空间的长度。 而这个长度，实际上就是包含第i个数字的最长的魔法空间的长度再加上1！
           没错，对于F来讲， 依然是一个动态规划问题，不过是一个非常简单的动态规划问题：

            F(i+1)=F(i)+1           (3)

           但是我们仍然要拿到mark[num[i+1]], 因为前一个与第i+1个数字相同的数字J可能包含于F(i)所代表的魔法区间中， 而现在因为加入了i+1个数字，所以J会“截断”F(i).

          所以对于这个问题，我们不必再去回溯（也就是说现在的时间复杂度是On ）, 只需在考察第i+1个数字时，分析两种情况：

          包含第i个数字的最长空间不含有与i+1 相同的数字： 那么F（i+1）=F(i)+1 

          否则 F(i+1)= i+1 -j .


          注意文章中的变量名称与程序不是完全对应的。程序的实现手段可能更加抽象， 但是思路就是上文所述。

          代码敬上

       

#include<iostream>
#include<algorithm>
using namespace std;
int num[1000001];
int limit[1000001];
int max_[1000001];
int main()
{
    int i,j,n,T;
    scanf("%d",&T);
//    scanf_(T);
    while(T--)
    {
        scanf("%d",&n);
    //    scanf_(n);
        memset(max_,-1,sizeof(max_));
        for(i=0;i<n;i++)
        {
            scanf("%d",&num[i]);
            //scanf_(num[i]);
        }
        int sum=1;
        max_[num[0]]=0;
        limit[0]=0;
        for(i=1;i<n;i++)
        {
        
            if(max_[num[i]]<limit[i-1])
            {
                sum+=(i-limit[i-1]+1);
                limit[i]=limit[i-1];
            }
            else
            {
                
                sum+=i-max_[num[i]];
                limit[i]=max_[num[i]]+1;
                
            }

            max_[num[i]]=i;
            
        }
        printf("%d\n",sum);
    }
}

              

      






动态规划解不包含相同数字的子串个数问题


联系
我们