山科交流試合-LIS

Description
長さnのシーケンス(n<=1000)を与え、そのシーケンスLIS(最長上昇サブシーケンス)の長さmを記し、そのシーケンスの中でどのくらいの位置が異なる長さmの厳密な上昇サブシーケンスがあるかを求める.
Input
まずTを入力して、以下にいくつかのデータがあることを示します.
各データのセットにnを入力し、配列サイズを示します.
次の行のn個の数はこの配列を表し、1<=a[i]<=nである.
Output
出力は1行で、上記要求の個数(出力保証結果は2^31未満)を出力するだけです.
Sample Input

3
2
1 2
4
1 2 4 4
5 
1 2 3 4 5

Sample Output

1
2
1

分析:最長でシーケンスの変形から下がらないで、この問題を始めて、考慮していないところはとても多くて、例えばバケツで重さを排出したいのですが、同じ元素が不連続な状態であれば無視しました;重量除去方式を変え、連続的に重量を除去する.位置の違いを探します.これは、各要素の前の最長シーケンスの長さを意味します.要素がそれより小さい場合は、この位置が最も長く、サブシーケンスが下がらない可能性(位置が異なる)を示します.

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int tt;
    scanf("%d",&tt);
    while (tt--)
    {
        int n;
        scanf("%d",&n);
        int a[1005],c[1005];
        int b,t=0;
        for (int i=0;i<n;i++)  //  
        {
            scanf("%d",&b);
            if (t!=0 && a[t-1] == b) c[t-1]++;
            else a[t]=b,c[t++]=1;
        }
        int f[1005],g[1005];
        memset(g,0,sizeof(g));//     
        f[0]=1;
        g[0]=1;
        int ans=0;
        int Max=0,pos=0;
        for (int i=1;i<t;i++)
        {
            Max=0;
            for (int j=0;j<i;j++)//   i       
            {
                if (a[i]>a[j])
                {
                    Max=max(Max,f[j]);
                }
            }
            for (int j=0;j<i;j++)
            {
                if (a[i] > a[j] && f[j] == Max)
                {
                    if (g[j] == 0) g[j]=1;//   
                    g[i]+=g[j]*c[i];
                }
            }
            f[i]=Max+1;
            if (f[i] > ans)
            {
                ans=f[i];
            }
        }
 
        int sum=0;
        for (int i=0;i<t;i++)
            if (f[i] == ans) sum+=g[i];
        cout<<sum<<endl;
    }
    return 0;
}
 
/**************************************************************
    Problem: 1800
    User: 1505180117
    Language: C++
    Result: Accepted
    Time:96 ms
    Memory:1268 kb
****************************************************************/