hdu 4455 dp

제목: 서열ai를 정하고 개수는 n입니다.일련의 w 더 주기;모든 w에 대해 서열에서 모든 길이가 w인 연속 서브열의 값과 서브열의 값은 서브열의 다른 수의 개수를 구한다
 
몇 개의 서류를 가져간 후에 마침내 A가 되었다
 
예를 들면 다음과 같습니다.
1 1 2 3 4 4 5;
뚜렷한 dp[1]=n=7;
길이가 1일 때는 7개의 구간이 있다.길이가 1에서 2까지 전 6개 구간을 뒤로 한 수를 늘려 마지막 구간을 빼는 것이다.
추가된 6개의 수는 이 구간에 나타났는지의 여부를 보아야 하며, 이전의 같은 원소의 거리가 2보다 큰지 보아야 한다
그래서 dp[2]=dp[1]-1+4;
이런 식으로 유추하면 그래서 dp값을 얻어낼 수 있다.
dp[i]=dp[i-1]-A+B;
줄인 A는 마지막 길이가 i-1인 구간의 다른 수의 개수인데 이것은 예처리하기 쉽다.
덧붙인 B는 t번째로 셀 수 있는데 그 위의 수의 거리는 i-1의 개수보다 크다.
이 B값도 쉽게 나온다.
s[i]로 이전 수의 거리가 i인 개수를 표시하고 끊임없이 줄이면 B를 얻을 수 있다.

 1 #include<cstdio>

 2 #include<cstring>

 3 using namespace std;

 4 #define ts printf("*****
");

 5 #define cl(a) memset(a,0,sizeof(a))

 6 const int maxn=1000007;

 7 long long dp[maxn];

 8 int dis[maxn]; // i                 1，2，1    d[3]=2

 9 int r[maxn]; //             i   

10 int vis[maxn];

11 int lastp[maxn]; // i        

12 int a[maxn];

13 int dif[maxn]; // n-i+1 n       

14 

15 int main()

16 {

17     int i,j,k;

18     #ifndef ONLINE_JUDGE

19     freopen("1.in","r",stdin);

20     #endif

21     int n;

22     while(scanf("%d",&n)!=EOF)

23     {

24         if(n==0)    break;

25         cl(lastp);

26         for(i=1;i<=n;i++)

27         {

28             scanf("%d",a+i);

29             dis[i]=i-lastp[a[i]];

30             lastp[a[i]]=i;

31         }

32         cl(r);

33         for(i=1;i<=n;i++)

34         {

35             r[dis[i]]++;

36         }

37         cl(dif);

38         cl(vis);

39         int t=0;

40         for(i=n;i>0;i--)

41         {

42             if(!vis[a[i]])

43             {

44                 vis[a[i]]=1;

45                 t++;

46             }

47             dif[n-i+1]=t;

48         }

49         int sum=n;

50         cl(dp);

51         dp[1]=n;

52         for(i=2;i<=n;i++)

53         {

54             dp[i]+=dp[i-1]-dif[i-1];//            

55             sum-=r[i-1];

56             dp[i]+=sum;

57         }

58         int q,tt;

59         scanf("%d",&q);

60         while(q--)

61         {

62             scanf("%d",&tt);

63             printf("%I64d
",dp[tt]);

64         }

65     }

66     return 0;

67 }