hdu 4455 dp

9639 단어 HDU
제목: 서열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 }

좋은 웹페이지 즐겨찾기