首页 > ACM题库 > HDU-杭电 > HDU 4455-Substrings-动态规划-[解题报告]HOJ
2015
07-16

HDU 4455-Substrings-动态规划-[解题报告]HOJ

Substrings

问题描述 :

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

输入:

There are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a1,a2…an, 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<w<=n<=106, 0<=Q<=104, 0<= a1,a2…an <=106

输出:

There are several test cases.
Each test case starts with a positive integer n, the array length. The next line consists of n integers a1,a2…an, 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<w<=n<=106, 0<=Q<=104, 0<= a1,a2…an <=106

样例输入:

7
1 1 2 3 4 4 5
3
1
2
3
0

样例输出:

7
10
12

题意:

给定一个序列ai,个数为n。再给出一系列w;对于每个w,求序列中,所有长度为w的连续子串中的权值和,子串权值为子串中不同数的个数

题解:

一道动态规划体。。一开始i想成了树状数组。dp[i表示w=i时所求的答案。dp[1]=n,这个很容易知道,dp[2]中的子串就是删去dp[1]中最后一个子串,再每个子串加上其之后的那个数,以此类推。。

要删去的最后一个子串的权值很好求,for以遍就能预处理,num[i]表示w=i的最后一个子串权值。难的就是求加上一个数后所加的权值:另c[i]表示一个数与它前面值相同的最近距离,这也能for一遍预处理。之后求出sum[i],表示两同值数最短距离大于等于i的值。对于dp[i-1]推dp[i],加上一个数,只有当这个数与它前面同值数最短距离大于等于i时才会加权值,否则会重复而不加。所以可以推出递推式:dp[i]=dp[i-1]-num[i-1]+sum[i],dp[1]=n;

注意:

1.处理c[i]的时候,如果一个数ai前面没有相同的数,则距离计算为到0的距离i,why?因为加上这类数也是成立。

2.答案dp[i]会超int,我就wa了好几次。。

耗时:593MS/5000MS

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef __int64 LL;
const int maxn=1e6+10;
int c[maxn],a[maxn],pre[maxn],sum[maxn],num[maxn];
LL dp[maxn];
int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)break;
        int i,j,k,t;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(c,0,sizeof(c));
        memset(pre,0,sizeof(pre));
        for(i=1;i<=n;i++)
        {
            c[i-pre[a[i]]]++;//pre[a[i]]=0的也是可以的
            pre[a[i]]=i;
        }
        sum[n]=c[n];
        for(i=n-1;i>=1;i--)
            sum[i]=sum[i+1]+c[i];
        memset(c,0,sizeof(c));
        num[1]=1;
        c[a[n]]++;
        for(i=2;i<=n;i++)
        {
            if(c[a[n-i+1]]==0)
            {
                num[i]=num[i-1]+1;
                c[a[n-i+1]]=1;
            }
            else
            num[i]=num[i-1];
        }
        dp[1]=n;
        for(i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]-num[i-1]+sum[i];
        }
        //for(i=1;i<=n;i++)
        //cout<<i<<":"<<num[i]<<" "<<sum[i]<<" "<<dp[i]<<endl;
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d",&t);
            printf("%I64d\n",dp[t]);
        }
    }
    return 0;
}
/*
10
1 1 2 1 2 2 3 2 1 2
1:10
2:16
3:17
4:17
5:16
6:14
7:12
8:9
9:6
10:3

*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/a601025382s/article/details/12283581