hdu 4455 dp
9639 단어 HDU
몇 개의 서류를 가져간 후에 마침내 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 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.