題目意思我的想法:首先把一些能表達的數給算出來,存起來.然后再看是不是都能表示或者沒有最大值.算出能表達的數我采用的是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;
}