hdu 4455 Substrings(找规律&DP)

SubstringsTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1161 Accepted Submission(s): 351


Problem DescriptionInputOutputSample InputSample OutputSource#include <iostream>#include<string.h>#include<stdio.h>using namespace std;const int maxn=1000010;int a[maxn],pre[maxn],len[maxn];__int64 dp[maxn],rest;//注意数据范围呀！！bool vis[maxn];int main(){ int n,q,w,i; while(scanf("%d",&n),n) { memset(pre,-1,sizeof pre); memset(len,0,sizeof len); memset(vis,0,sizeof vis); for(i=0;i<n;i++) { scanf("%d",a+i); len[i-pre[a[i]]]++;//统计各长度的数目 pre[a[i]]=i; } for(i=n-1;i>=0;i--) len[i]+=len[i+1];//len[i]代表长度大于等于i的个数 dp[0]=0; dp[1]=n; rest=1; vis[a[n-1]]=true; for(i=2;i<=n;i++) { dp[i]=dp[i-1]+len[i]-rest;//rest为长度不足i的部分 if(!vis[a[n-i]]) { rest++; vis[a[n-i]]=true; } } scanf("%d",&q); while(q--) { scanf("%d",&w); printf("%I64d\n",dp[w]); } } return 0;}