191101苦练搜索

震惊！ZJ某中苦练搜索暴力出奇迹 敲黑板敲黑板敲黑板 关于搜索剪枝的一点思考 剪枝的两个角度 1 最大限制：超过了最大限制一定不优 2 最优答案：如果剩下的所有（剩余的量）都加上，还达不到（不一定是大）目前最优的答案，那么一定不优 还要建立一个习惯——预估M和T会不会超 常见数据范围: 搜索——n<100 DP——n>100&&n<10000 高级的算法，二分之类（带log）——n>100000

T1 transq

可以用状压的思想 不过为了苦练搜索，我们采用这种方式

审题啊！一个实数卡我半个小时 一眼望去背包DP 有实数！！！ 于是读优GG，DPGG 可以用状压的思想 可以回溯

最劣情况：每一种都搜一下 $O(2^N)\Rightarrow 2^{30}>10^8$ 因此必须剪枝 优化1：目前重量>最大载重，return; 优化2：当前总val+剩下所有val_{倒序求’后缀和’}<ans（目前求出的最优答案），return;

代码如下

#include<bits/stdc++.h> using namespace std; #define in Read() #define re register #define NNN 100 int n; double w[NNN],v[NNN],ans,f[NNN],x; bool exist[NNN],best[NNN]; //inline int in{ // int i=0,f=1;char ch; // while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); // if(ch=='-'){ // ch=getchar();f=-1; // } // while(ch>='0'&&ch<='9')i=(i<<1)+(i<<3)+ch-48,ch=getchar(); // return i*f; //} inline void Dfs(int step,double wei,double val){ if(wei>x)return;//¼ôÖ¦1 if(step>n) if(val>ans){ ans=val; for(re int i=1;i<=n;i++) best[i]=exist[i]; return ;//СÐÄŶ~ ±ß½çÌõ¼þµÄ¹Ø¼ü¾ÍÊÇreturn } if(val+f[step]<ans)return;//¼ôÖ¦2 exist[step]=true; Dfs(step+1,wei+w[step],val+v[step]); exist[step]=false; Dfs(step+1,wei,val); return ; } int main(){ scanf("%lf%d",&x,&n); for(re int i=1;i<=n;i++)scanf("%lf%lf",&w[i],&v[i]); for(re int i=n;i>=1;i--)f[i]=f[i+1]+v[i];//Ô¤´¦Àí:ºó׺ºÍ Dfs(1,0,0); printf("%d\n",(int)ans); for(re int i=1;i<=n;i++) if(best[i]) printf("%d ",i); return 0; }

T2 dispatch

不管那么多,直接考虑优化

优化1: 最大限制 优化2: 从大到小排序, 筛去无效分支(有点类似于贪心) 优化3: 最优答案

小心time的关键词冲突

代码如下

#include<bits/stdc++.h> using namespace std; #define in Read() #define re register #define INF 2147483647 int n,k,ans=INF; int t[20],Time[10]; inline int in{ int i=0,f=1; char ch; for(ch=getchar();(ch>'9'||ch<'0')&&ch!='-';ch=getchar()); if(ch=='-'){ ch=getchar();f=-1; } for(;ch>='0'&&ch<='9';ch=getchar())i=ch-48+(i<<1)+(i<<3); return f*i; } inline bool comp(const int &a,const int &b){ return a>b; } inline void Dfs(int step,int maxt){ if(maxt>=ans)return ; if(step>n){ //已经把>ans的情况剪掉了,不需要再比较就可以直接更新答案 ans=maxt; return ; } for(re int i=1;i<=k;i++){ if(Time[i]+t[step]>ans)continue ;//又一个剪枝 小心不是return哦~ Time[i]+=t[step]; Dfs(step+1,max(maxt,Time[i]));//以最久的时间为准 Time[i]-=t[step];//要取消 } return ; } int main(){ n=in,k=in; for(re int i=1;i<=n;i++)t[i]=in; sort(t+1,t+n+1,comp); Dfs(1,0); printf("%d",ans); return 0; }