描述百度应用平台上有很多有趣的应用，每个应用都由一个开发者开发，每个开发者可能开发一个或多个应用。百度的工程师们想把应用尽可能好的推荐给用户。
-
研究发现，同一个开发者开发的程序的图标有很大的相似性。如果把同一个开发者开发的应用放在一起，用户很快就会厌倦相似的图标，如果把这些图标穿插摆放效果就会好很多。
现在工程师想给用户推荐来自m个开发者的n个应用，在推荐的时候这些应用的图标将排成整齐的一行展示给用户，相邻两个图标之间的距离正好是1，工程师们想让这些图标尽可能的穿插摆放。为了衡量穿插摆放的效果，给每个图标定义一个“分离度”，分离度的值是指当前图标和它左边最近的来自同一个开发者的图标之间的距离。如果一个图标左边没有来自同一个开发者的图标，则分离度为0。所有图标穿插摆放效果的值定义为所有图标的分离度之和。
已知每个开发者开发的应用个数，请帮助百度的工程师找到图标穿插摆放效果的最大值。
- 输入
-
输入的第一行包含两个整数n和m，用一个空格分隔，分别表示应用的个数和开发者的个数。
第二行包含m个正整数，相邻两个数之间用一个空格分隔，表示每个开发者开发的应用个数，这些整数之和必然等于n。
- 输出
-
输出一个整数，表示图标穿插摆放效果的最大值。
- 样例输入
-
8 3
3 3 2
- 样例输出
- 15
- 提示
-
- #include"stdio.h"
- #include"malloc.h"
- int total,kind,number,record=0;//record表示最高纪录
- void swap(int& a,int& b)//输出list中第i到第n个字符的全排列
- {
- int t;
- t=a;
- a=b;
- b=t;
- }
- void calc(int list[])
- {
- number=0;
- int i,j,flag=0,first=0,last=0;
- for(i=0;i<total-1;i++)
- {
- if(list[i]==list[i+1])//如果相邻两个相同则不符合条件
- goto end;
- }
- for(i=1;i<=kind;i++)
- {
- for(j=0;j<total;j++)
- {
- if(i==list[j]&&flag==0)
- {
- flag=1;
- first=j;
- }
- else if(i==list[j])
- {
- last=j;
- }
- }
- number+=(last-first);
- flag=0;
- }
- if(number>record)
- record=number;//更新record纪录
- number=0;
- end:;
- }
- void perm(int list[],int k,int m)
- {
- int i;
- if(k==m)
- calc(list);//计算找出分离度
- else
- for(i=k;i<=m;i++)
- {
- swap(list[k],list[i]);
- perm(list,k+1,m);
- swap(list[k],list[i]);
- }
- }
- void main()
- {
- int n,m,i,j,k=0,*a,*b;
- scanf("%d%d",&n,&m);
- total=n;//总个数
- kind=m;//种类
- a=(int *)malloc(m*sizeof(int));//m=3
- b=(int *)malloc(n*sizeof(int));//n=8
- for(i=0;i<m;i++)
- scanf("%d",a+i);
- for(i=0;i<m;i++)
- for(j=0;j<*(a+i);j++)
- *(b+(k++))=i+1;//用递增的数字表示图标，相同的数字表示有一个程序员开发出来的图标
- perm(b,0,n-1);
- printf("%d\n",record);
- }
对于20%的数据，n≤ 10；
对于40%的数据，n≤ 100。
对于100%的数据，1≤ m ≤ n ≤ 100,000
本文出自 “阿凡达” 博客，请务必保留此出处http://shamrock.blog.51cto.com/2079212/702552