社区讨论
为什么会RE
P1048[NOIP 2005 普及组] 采药参与者 4已保存回复 14
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 14 条
- 当前快照
- 1 份
- 快照标识符
- @mi6wm0wv
- 此快照首次捕获于
- 2025/11/20 12:01 4 个月前
- 此快照最后确认于
- 2025/11/20 15:06 4 个月前
/*
@Date : 2018-08-24 08:15:21
@Author : Adscn (1349957827@qq.com)
Link : https://www.cnblogs.com/LLCSBlog
/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define pi(k) putint(k)
#define gc getchar()
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while((ch<'0')|(ch>'9'))ch=='-'?f=1:f,ch=gc;
while((ch>='0')&(ch<='9'))xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
IL void putint(int k)
{
if(k<0)k=-k,putchar('-');
if(k>=10)putint(k/10);
putchar(k%10+'0');
}
int n,m,ans;
struct object
{
int weigh;
int val;
} pl[101];
double mutation=0.7RAND_MAX;//0.5233
double crossover=1RAND_MAX;
const int NUM=20;
struct DNA
{
// vectors;
bool s[101];
int val;
inline void init(int n)
{
//s.resize(n+1);
for(register int i=1; i<=n; i++)s[i]=rand()&1;
val=getval();
}
inline int getval() //计算答案
{
int ans=0,bag=m;
for(register int i=1; i<=n; i++)
{
if((!s[i])&&bag>=pl[i].weigh)
{
ans+=pl[i].val;
bag-=pl[i].weigh;
}
}
return ans;
}
/ inline void clear()
{
vector().swap(s);
}*/
}lif[2][NUM+1];
DNA * life=lif[0];
unsigned long long sum;
double P[NUM+1];
bool now;
inline void init()
{
for(register int i=1; i<=NUM; i++)life[i].init(n);
}
inline int choice()
{
double m=0;
double r=(double)rand()/RAND_MAX;
for(int i=1;i<=n;i++){m+=P[i];if(r<=m)return i;}
return n;
}
DNA fa,mo;
inline void competition()
{
sum=0;
int xmax=0,xval=0,xxmax;
for(int i=1;i<=NUM;i++)
{
sum+=life[i].val;
if(life[i].val>ans)ans=life[i].val;
if(life[i].val>xval)xxmax=xmax,xmax=i,xval=life[i].val;
}
for(int i=1;i<=NUM;i++)P[i]=(double)life[i].val/sum;
int cnt=0;now=!now;
lif[now][++cnt]=life[xmax],lif[now][++cnt]=life[xxmax];
do{
fa=life[choice()],mo=life[choice()];
if(crossover>rand())
{
int midl=rand()%n+1,midr=rand()%(n-midl+1)+midl;
for(int i=midl;i<=midr;i++){bool tmp=fa.s[i];fa.s[i]=mo.s[i],mo.s[i]=tmp;}
}
if(mutation>rand()){int ars=rand()%n+1;fa.s[ars]=!fa.s[ars];}
if(mutation>rand()){int ars=rand()%n+1;mo.s[ars]=!mo.s[ars];}
fa.val=fa.getval(),mo.val=mo.getval();
lif[now][++cnt]=fa,lif[now][++cnt]=mo;
//fa.clear(),mo.clear();
}while(cnt<NUM);
life=lif[now];
}
inline void work()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
m=gi,n=gi;
for(register int i=1; i<=n; i++)
{
pl[i].weigh=gi;
pl[i].val=gi;
}
int l=1000000;
int lans=0,cnt=0;
while(l--){competition();/if(ans>lans)putint(lans=ans),putchar('\n'),cnt=0;else cnt++;/}
printf("%d",ans);
}
int main(void)
{
srand((unsigned(time(NULL))));
work();
return 0;
}
回复
共 14 条回复,欢迎继续交流。
正在加载回复...