### jiangxiong's blog

By jiangxiong20 months ago, ,

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;
}

``````

•
• +6
•

 » 20 months ago, # |   0 Thanks for those tips given by my friend zzyzzy12