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

比赛描述

输入

输出

样例输入

样例输出

提示

#include
#include
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>num[i];
        }
        int sum=0;
        for(i=0;i=limit;j--)
            {
                if(num[j]==num[i])
                    break;
                temp++;
                if(mark[j]>limit)
                    limit=mark[j];
            }
            mark[i]=j+1;
        //    cout<

          这个做法并非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
#include
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



      

















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