HDU-4455

2018-03-06

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4455

题目大意

给定一个长度为N的字符串和一个数w，求所有相邻w个数的不同的数的数量之和。

思想

首先表示状态，dp[i]表示所有相邻i个数的不同的数的数量之和。
再划分阶段，我们观察得到，i每增加1，对于每个分组其实就是删除最后一个分组，其他每个分组向后扩展一位。
对于相邻i个数时的dp[i]，就是相当于dp[i-1]-A+B，其中，A是相邻i-1时的最后一个分组的不同数的数量，B是新增加一位后，整体增加的不同数的数量和。

值得一提的是，在这里维护A和B的技巧性都很强。
一开始我的TLE的代码的维护办法：
预处理出dis[i]表示第i个位置的数距离前面与他相同的数的长度。
维护A：每次维护dp[i]，都从第N-i+1遍历到第N个数，判断dis是不是超出了最后一个分组的范围。
维护B：从第i个遍历至第N个，判断dis是不是超出了当前分组长度。
AC维护办法：
预处理出dis[i]，dis[i]表示：假设当前位置为t，arr[t]为位置t的值，pos[t]为上一个arr[t]的位置，那么dis就表示t-pos[arr[t]]==i的数量。
维护A：开辟数组f[i]表示i在最后一个分组中是否出现过，最后一个分组相当于向前每次扩展一位，判断新扩展的这一位f是不是为1，为1说明出现过，为0说明没出现过，然后设为1。该方法不需要在每次DP中都从头循环一次，可以预处理好，也可以跟着dp一个一个处理。
维护B：记sum=N，表示一开始分组每组数量为1时的不同数之和。每一次更新dp[i]的时候，sum-=dis[i-1]，也就是减去恰好在分组范围内的个数。因为sum是有后效性的，所以第一次减dis[1]，第二次减dis[2]……以此类推，到第i次的时候，就已经相当于减去了距离为1……i-1的所有重复的数，也就是还剩下的新增的不同的数的数量。

代码

HDU-4455

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1000005
#define MAXQ 10005
int N,Q;
int arr[MAXN],pos[MAXN],dis[MAXN];
long long dp[MAXN];
int lastdiff[MAXN],f[MAXN];
int main()
{
    while (scanf("%d",&N) && N)
    {
        memset(pos,0,sizeof(pos));
        memset(dis,0,sizeof(dis));
        for (int i=1;i<=N;i++)
        {
            scanf("%d",&arr[i]);
            dis[i-pos[arr[i]]]++;
            pos[arr[i]]=i;
        }
        dp[1]=N;

        memset(f,0,sizeof(f));
        lastdiff[1]=1;
        f[arr[N]]=1;
        int add=N;
        for (int i=2;i<=N;i++)
        {
            if (f[arr[N-i+1]] == 0)
            {
                f[arr[N-i+1]]=1;
                lastdiff[i]=lastdiff[i-1]+1;
            }
            else
                lastdiff[i]=lastdiff[i-1];
            add-=dis[i-1];
            dp[i]=dp[i-1]-lastdiff[i-1]+add;
        }
        scanf("%d",&Q);
        for (int i=1;i<=Q;i++)
        {
            int q;
            scanf("%d",&q);
            printf("%I64d\n",dp[q]);
        }
    }
    return 0;
}

后记

比较有难度的DP还是没办法自己独立做出来，从状态的表示到阶段的划分，感觉每个题都毫无规律可循。。很伤心。。
回去还得写近世代数作业。。还要洗衣服。。
心塞塞啊。。