hdu--4455+Substrings+2012杭州地区試合C題+DP

久しぶりにブログを書いて、次のブログを見ても8月の最後の日に書いたので、アリが変化を抱擁しているので、仕事を探していました.9月に仕事を見つけて、10月にまた1ヶ月も考えていましたが、実はすべて必要ありません.考えても何の問題も解決できないことを理解しなければなりません.本当に得られないことを強要する必要はありません.自然にしましょう.がんばれ、少年!!
テーマリンク:午后の训练に入る时、この问题をクリックして何时间も考えても全然考えられませんが、心を静めるといくつかの规则が见られます.まずw=i+1の場合はw=iの場合と関係があり、具体的にはdp[i]をw=iの場合の答えとし、w=i-1の場合を考慮すると、各セグメントの後に1つの数を加えればw=iの場合が得られる.しかし、w=i-1の場合の最後のセグメントは、1つの数を加えることでw=iを得ることができない場合があるので、この場合は削除しなければならない.この場合の数は計算しやすい.起点を最後の要素に固定し、現在の区間にいくつの異なる要素があるかを順番に前に押す必要があるからだ.そして難点は、w=i-1の場合、各セグメントに1つの数を加えて増加する場合数をどのように計算するかである.この点については,各数とその最近の同じ数の距離を事前に処理して計算することができ(同じ数がなければ原点との距離である),種々の異なる距離のケース数を統計した後,w=i−1を繰返し法で計算し,各セグメントに1つの数を加算することで増加したケース数を算出することができる.より具体的には、コードを参照してください.
コードは次のとおりです.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=1000010;
long long dp[maxn];
int sum[maxn],pre[maxn],dist[maxn];
int last[maxn],a[maxn];

int main()
{
    //freopen("in.txt","r",stdin);
    int n;
    while(scanf("%d",&n)&&n)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(pre,0,sizeof(pre));
        last[1]=1;
        pre[a[n]]=1;
        int cnt=2;
        for(int i=n-1;i>=1;i--)
        {
            if(pre[a[i]])
                last[cnt]=last[cnt-1];
            else
            {
                last[cnt]=last[cnt-1]+1;
                pre[a[i]]=1;
            }
            cnt++;
        }
        memset(pre,0,sizeof(pre));
        memset(dist,0,sizeof(dist));
        for(int i=1;i<=n;i++)
        {
            dist[i-pre[a[i]]]++;
            pre[a[i]]=i;
        }
        sum[n]=dist[n];
        for(int i=n-1;i>=1;i--)
        {
            sum[i]=sum[i+1]+dist[i];
        }
        dp[1]=n;
        for(int i=2;i<=n;i++)
            dp[i]=dp[i-1]-last[i-1]+sum[i];
        int m;
        scanf("%d",&m);
        while(m--)
        {
            int x;
            scanf("%d",&x);
            printf("%lld
",dp[x]);
        }
    }
  return 0;
}