BZOJ2914: [Poi1997]ADDON【01背包】

2914: [Poi1997]ADDON

【题目描述】

传送门

【题解】

燃料室高度的最大可能值应该指的是第一个高度不在稳定高度集合里的数。
这题其实就是一个背包就可以了。

代码如下

#include<cstdio>
#include<algorithm>
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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部