社区讨论

为什么会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 条回复,欢迎继续交流。

正在加载回复...