洛谷P2329 [SCOI2005]栅栏题解

深碍√TFBOYSˉ_ 2023-06-01 15:53 12阅读 0赞

### 洛谷P2329 \[SCOI2005\]栅栏 题解 ###

[题目描述][Link 1]

这道题是去ZR的时候老师讲的，题目思路比较简单，就是二分答案，然后爆搜判断是否可行。对，就是枚举全排列的那种爆搜，但是时间复杂度显然不对，是\\(O(m^n)\\)，但是好像只能这样做。

70分 直接爆搜

// luogu-judger-enable-o2 #include<algorithm> #include<iostream> #include<cstdio> using namespace std; const int M=55,N=1e3+100; int n,m; int a[M],b[N],a1[M],b1[N]; inline int dfs(int x,int n) { if (x==n+1) return 1; bool p; for (int i=1;i<=m;i++) if (a1[i]-b1[x]>=0) { a1[i]-=b1[x]; p=dfs(x+1,n); if (p) return 1; a1[i]+=b1[x]; } return p; } inline void pre() { for (int i=1;i<=m;i++) a1[i]=a[i]; for (int i=1;i<=n;i++) b1[i]=b[i]; return ; } inline bool cmp(int x,int y) { return x>y; } int main() { scanf("%d",&m); for (int i=1;i<=m;i++) scanf("%d",a+i); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",b+i); sort(b+1,b+n+1); sort(a+1,a+m+1,cmp); int l=0,r=n,mid=(l+r)>>1; while (l<=r) { pre(); if (dfs(1,mid)) l=mid+1; else r=mid-1; mid=(l+r)>>1; } printf("%d",mid); return 0; }

然后还有一些剪枝

*  浪费的木板长度加上要拼的木板长度小于木板总长度，剪掉
 *  当前要拼木板的长度和大于总木板长度，连搜都不用搜，直接剪掉

其实加上这两个剪枝就可以\\(AC\\)，但是因为剪枝好像写假了，就得了80分。

然后我又倒着搜了一下，100分。

#include<algorithm> #include<iostream> #include<cstdio> using namespace std; const int M=55,N=1e3+100; int n,m,tot,w; int a[M],b[N],L[M],sum[N]; inline bool dfs(int x) { if (!x) return 1; if (w+sum[x]>tot) return 0; for (int i=1;i<=m;i++) if (L[i]-b[x]>=0) { L[i]-=b[x]; if (L[i]<b[1]) w+=L[i]; if (dfs(x-1)) return 1; L[i]+=b[x]; } return 0; } inline bool check(int mid) { for (int i=1;i<=m;i++) L[i]=a[i]; w=0; if (sum[mid]>tot) return 0; return dfs(mid); } int main() { scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d",a+i); tot+=a[i]; } scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",b+i); sort(a+1,a+m+1); sort(b+1,b+n+1); for (int i=1;i<=n;i++) sum[i]=sum[i-1]+b[i]; int l=0,r=n,mid=(l+r)>>1,ans; while (l<=r) { if (check(mid)) { ans=mid; l=mid+1; } else r=mid-1; mid=(l+r)>>1; } printf("%d\n",ans); return 0; }

收获：

> 有时候倒着搜比较好，还可以少写一个变量，时间复杂度\\(O(玄学)\\)

转载于:https://www.cnblogs.com/last-diary/p/11400192.html

[Link 1]: https://www.luogu.org/problem/P2329