题目意思我的想法:首先把一些能表达的数给算出来,存起来.然后再看是不是都能表示或者没有最大值.算出能表达的数我采用的是dp.这里的dp,比如说有给你三个数3 6 10要你求用这三个数能表达的一系列数,首先我用一个数组can[]记录所有能表达的数,can[i]=j表示这些能表达的数按升序排列地i个是j.再用数组记录下3 6 10这三个数和can数组里面的某个数相加时所到的下表(说的很拗口- -)
比如说我用idx[0]记录3这个数和can数组的第idx[0]个数相加,idx[1]表示6和can数组的第idx[1]个数相加.等等。下面用具体写下过程.
首先置can[0] = 0 idx[0] = idx[1] = idx[2] = 0;(也就是说3 6 10接下来会和can数组的第0个相加)
下标 0 1 2 3 4 5
can 0 3(3+can[0]) 6(3+can[1]/6+can[0]) 9(3+can[2]/6+can[1]) 10(10+can[0]) 12(3+can[3]/6+can[2])
3 idx[0] 0 1 2 3 3 4
6 idx[1] 0 0 1 2 2 3
10 idx[2] 0 0 0 0 1 1
中间我还加了些东西,也就是说如果只有一个元素的话,那么一定是输出0的(要不是都能表示[这个数是1]要不是无最大值)
如果有一个元素是1的话,那么一定输出0(所有的都能表示)
如果只有两个数的话,那么我们可以直接得到答案,如果两个数互素的话,结果是a*b-a-b,如果不互素的话输出0(无最大值)
如果是等差数列的话,输出0(无最大值)
其他的就直接算出能表示的数,再判断输出什么
官方的解题报告说
只要所有的数的gcd不是1就没有最大值,其实这一点可以由上面2个数的公式推出来,也就是先求前n-1个数的gcd然后再求gcd和第n个数的gcd,那么这样的话,这题还有一个数论方法,也就是直接算前n-1个数的gcd,然后看这个gcd和第n个数的gcd是否为1,不为1就输出0,为1就用a*b-a-b这个公式算
代码如下
/*
ID:qcx97811
LANG:C++
PROG:nuggets
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int n;
int num[16];
int idx[16],total_idx;
int can[2000000];
int cmp(const void *a,const void *b)
{//快速排序从小到大模板
int *c = (int *)a;
int *d = (int *)b;
if(*c > *d)
return 1;
if(*c == *d)
return 0;
return -1;
}
int gcd(int a,int b)
{//公约数
int tmp;
if(a < b)
{
tmp = a;
a = b;
b =tmp;
}
while(b)
{
tmp = a;
a = b;
b = tmp%b;
}
return a;
}
int main(void)
{
freopen("nuggets.in","r",stdin);
freopen("nuggets.out","w",stdout);
int i,j;
int k,tmp;
scanf("%d",&n);
for(i = 0;i < n;i++)
{//scanf
scanf("%d",&num[i]);
}
qsort(num,n,sizeof(num[0]),cmp);//sort the number
if((1 == num[0]) || (1 == n))
{//only one num or an one in the num
printf("0\n");
return 0;
}
else
{
memset(idx,0,sizeof(idx));
memset(can,0,sizeof(can));
if(2 == n)
{//2个数的话可以直接算出来
if(1 == gcd(num[0],num[1]))
{//如果互素的话
printf("%d\n",num[0]*num[1]-num[0]-num[1]);
return 0;
}
else
{//不互素 肯定无
printf("0\n");
return 0;
}
}
tmp = num[1] - num[0];
for(i = 2;i < n;i++)
{//看是否为等差数列
if(num[i]-num[i-1] != tmp)
break;
}
if(i == n)
{//如果是等差数列的话 也不可能有
printf("0\n");
return 0;
}
can[0] = 0;
total_idx = 0;
for(i = num[0];i < 2000000;i++ )
{//下标是为了不超过内存16M 同时最大
j = 0;
for(k = 1;k < n;k++)
{//增大能表示的数
if(num[k]+can[idx[k]]<num[j]+can[idx[j]])
j = k;
}
tmp = num[j]+can[idx[j]];
can[++total_idx] = tmp;
if(total_idx > num[0]-1 && (can[total_idx]-can[total_idx-num[0]+1] == num[0]-1))
{//如果已经找到最大数,因为后面的数都连续了
tmp = total_idx-num[0]+1;
while(can[tmp] - can[tmp-1] == 1)
{//寻找最大的数
tmp--;
}
printf("%d\n",can[tmp]-1);//输出最大数
return 0;
}
for(k = 0;k < n;k++)
{//改变相应的下标
if(num[k]+can[idx[k]] == tmp)
idx[k]++;
}
}
// for(i = 0;i <= total_idx;i++)
// printf("%d\n",can[i]);
printf("0\n");
}
return 0;
}