jiangxiong's blog

By jiangxiong, 12 years ago, In English

 this problem is similar to the Mixmum sum(http://poj.org/problem?id=2479); both of them could be solved in O(n) complexity; as my English is poor ,so I show the key idea in the above picture;

PS:the array rec[] in the codes has the same meaning with the array sum[] in the picture,and the array sum[] in the codes is just a temp variable used in the process of calculating the rec[]; and here is my code:

#include<cstdio>
#define MAX 200001

int last[MAX],next[MAX],max[MAX],input[MAX],sum[MAX],rec[MAX];

int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%d",&input[i]);
    for(int i=1;i<=n;i++)
    {
         int color=input[i];
         if(input[i]!=input[i-1])
         {
              next[last[color]]=i;
              last[color]=i;
         }
         sum[color]++;
         rec[i]=sum[color];
    }
    for(int i=0;i<=m;i++) last[i]=0;
    for(int i=1;i<=n;i++) if(last[input[i]]==0) last[input[i]]=i;
    for(int i=1;i<=n;i++)
    {
         int color=input[i];
         int same_color;
         while(true)
         {
              int total_color=i-last[color]+1;
              same_color=rec[i]-rec[last[color]]+1;
              int dis=total_color-same_color;
              if(dis<=k) break;
              last[color]=next[last[color]];
         }
         if(same_color>max[color]) max[color]=same_color;
    }
    int ans=0;
    for(int i=1;i<=m;i++) if(max[i]>ans) ans=max[i];
    printf("%d\n",ans);
    return 0;
}

  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?