HDU 4455 Substrings第37回ACM/ICCC杭州試合区現場試合C題(DP)
9455 ワード
Substrings
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 183 Accepted Submission(s): 42
Problem Description
XXX has an array of length n. XXX wants to know that, for a given w, what is the sum of the distinct elements’ number in all substrings of length w. For example, the array is { 1 1 2 3 4 4 5 } When w = 3, there are five substrings of length 3. They are (1,1,2),(1,2,3),(2,3,4),(3,4,4),(4,4,5)
The distinct elements’ number of those five substrings are 2,3,3,2,2.
So the sum of the distinct elements’ number should be 2+3+3+2+2 = 12
Input
There are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a
1,a
2…a
n, representing the elements of the array.
Then there is a line with an integer Q, the number of queries. At last Q lines follow, each contains one integer w, the substring length of query. The input data ends with n = 0 For all cases, 06, 0<=Q<=10
4, 0<= a
1,a
2…a
n <=10
6
Output
For each test case, your program should output exactly Q lines, the sum of the distinct number in all substrings of length w for each query.
Sample Input
7
1 1 2 3 4 4 5
3
1
2
3
0
Sample Output
7 10 12
Source
2012 Asia Hangzhou Regional Contest
この問題は考えにくいですが、問題を見ると、このデータの範囲を見て、クエリーの方法を見ます...木の形の配列や線分の木についてずっと考えています.
DPで解決しようと思えば難しくない.
DPの考え方O(n)複雑度で解決する.
例として、次のように説明します.
1 1 2 3 4 4 5;
明らかなdp[1]=n=7;
長さが1の場合は7区間あります.長さ1から長さ2まで、前の6つの区間を1つ後ろに増やし、最後の区間を取り除く.
増加した6つの数は、その区間で発生したかどうかによって決まります.前の等しい要素の距離が2より大きいかどうかを見てください.
だからdp[2]=dp[1]-1+4;
このように推すと,従ってdp値が得られる.
dp[i]=dp[i-1]-A+B;
減算Aは最後の長さi−1の区間の異なる数の個数であり,これは容易に前処理できる.
加算Bは、t番目の数からその前の数までの距離がi-1より大きい数である.
このB値も出やすいです.
前の数からの距離がiの数であることをs[i]で表し、どんどん減らしてBを得る.
具体的には、コードを参照してください.
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 183 Accepted Submission(s): 42
Problem Description
XXX has an array of length n. XXX wants to know that, for a given w, what is the sum of the distinct elements’ number in all substrings of length w. For example, the array is { 1 1 2 3 4 4 5 } When w = 3, there are five substrings of length 3. They are (1,1,2),(1,2,3),(2,3,4),(3,4,4),(4,4,5)
The distinct elements’ number of those five substrings are 2,3,3,2,2.
So the sum of the distinct elements’ number should be 2+3+3+2+2 = 12
Input
There are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a
1,a
2…a
n, representing the elements of the array.
Then there is a line with an integer Q, the number of queries. At last Q lines follow, each contains one integer w, the substring length of query. The input data ends with n = 0 For all cases, 0
4, 0<= a
1,a
2…a
n <=10
6
Output
For each test case, your program should output exactly Q lines, the sum of the distinct number in all substrings of length w for each query.
Sample Input
7
1 1 2 3 4 4 5
3
1
2
3
0
Sample Output
7 10 12
Source
2012 Asia Hangzhou Regional Contest
この問題は考えにくいですが、問題を見ると、このデータの範囲を見て、クエリーの方法を見ます...木の形の配列や線分の木についてずっと考えています.
DPで解決しようと思えば難しくない.
DPの考え方O(n)複雑度で解決する.
例として、次のように説明します.
1 1 2 3 4 4 5;
明らかなdp[1]=n=7;
長さが1の場合は7区間あります.長さ1から長さ2まで、前の6つの区間を1つ後ろに増やし、最後の区間を取り除く.
増加した6つの数は、その区間で発生したかどうかによって決まります.前の等しい要素の距離が2より大きいかどうかを見てください.
だからdp[2]=dp[1]-1+4;
このように推すと,従ってdp値が得られる.
dp[i]=dp[i-1]-A+B;
減算Aは最後の長さi−1の区間の異なる数の個数であり,これは容易に前処理できる.
加算Bは、t番目の数からその前の数までの距離がi-1より大きい数である.
このB値も出やすいです.
前の数からの距離がiの数であることをs[i]で表し、どんどん減らしてBを得る.
具体的には、コードを参照してください.
//============================================================================
// Name : HDU4455.cpp
// Author : kuangbin
// Version :
// Copyright : Your copyright notice
// Description :
// DP
//
//============================================================================
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int MAXN=1000010;
int a[MAXN];//1-n
int f[MAXN];//f[i] a[i] ,f[i]==0
int s[MAXN];//s[i] t-f[t]==i,1<=t<=n t , i
long long dp[MAXN];//
int ss[MAXN];//ss[i] i
int main()
{
int n;
int m;
while(scanf("%d",&n)==1 && n)
{
memset(f,0,sizeof(f));
memset(s,0,sizeof(s));
// s
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i-f[a[i]]]++;
f[a[i]]=i;
}
memset(f,0,sizeof(f));//f
ss[1]=1;
f[a[n]]=1;
for(int i=2;i<=n;i++)
{
if(f[a[n-i+1]]==0)
{
f[a[n-i+1]]=1;
ss[i]=ss[i-1]+1;
}
else ss[i]=ss[i-1];
}
dp[1]=n;
int sum=n;
// dp[i-1] dp[i] ， 1，
//
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1]-ss[i-1];//
sum-=s[i-1];
dp[i]+=sum;//
}
scanf("%d",&m);
int t;
while(m--)
{
scanf("%d",&t);
printf("%I64d
",dp[t]);
}
}
return 0;
}