2914: [Poi1997]ADDON

【题目描述】

【题解】

这题其实就是一个背包就可以了。

代码如下

#include
    
     #include
     
      using namespace std;int T,n,Ans,a[10005],O[10005],tot;bool f[10005];int main(){	scanf("%d",&n);Ans=0;	for(int i=1;i<=n;i++) scanf("%d",&a[i]);	f[a[n]+1]=1;tot=1;	for(int i=1;i<=a[n]+1;i++){		if(f[i]&&i!=a[tot]){Ans=a[tot-1];break;}		if(i==a[tot]){			if(!f[i]) O[++O[0]]=i,f[i]=1;			tot++;		}		if(f[i])		for(int j=1;j<=O[0];j++)		if(i+O[j]<=a[n]) f[i+O[j]]=1;	}	printf("%d\n",Ans);	for(int i=1;i<=O[0];i++) printf("%d\n",O[i]);	return 0;}