01 分數劃分

什么 01 分數劃分，叫 Binary Search 多好。

P1642 規劃

可以二分答案 \(x\)，考慮選擇 \(n-m\) 個數使得答案 \(\ge x\)。

\[\dfrac{\sum w(i)}{\sum c(i)}\ge x \]\[\sum w(i)\ge \sum (x\times c(i)) \]\[\sum(w(i)-x\times c(i))\ge 0 \]

之后按照改變后的權值 \(dp\) 出答案即可。

$\texttt{code}$ // Author:A weak man named EricQian #include<bits/stdc++.h> using namespace std; #define infll 0x7f7f7f7f7f7f7f7f #define inf 0x3f3f3f3f #define Maxn 105 typedef long long ll; inline int rd() {int x=0;char ch,t=0;while(!isdigit(ch = getchar())) t|=ch=='-';while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();return x=t?-x:x; } inline ll maxll(ll x,ll y){ return x>y?x:y; } inline ll minll(ll x,ll y){ return x<y?x:y; } inline ll absll(ll x){ return x>0ll?x:-x; } inline ll gcd(ll x,ll y){ return (y==0)?x:gcd(y,x%y); } int n,m,tot; int hea[Maxn],nex[Maxn<<1],ver[Maxn<<1]; int w[Maxn],c[Maxn],siz[Maxn]; double ans,d[Maxn],dp[Maxn][Maxn],tmp[Maxn]; inline void add(int x,int y){ ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot; } void dfs(int x,int fa) {dp[x][1]=d[x],siz[x]=1;for(int i=hea[x];i;i=nex[i]){if(ver[i]==fa) continue;dfs(ver[i],x);for(int j=1;j<=m;j++) tmp[j]=dp[x][j];for(int j=1;j<=min(siz[x],m);j++)for(int k=0;k<=m-j;k++)dp[x][j+k]=fmax(dp[x][j+k],tmp[j]+dp[ver[i]][k]);siz[x]+=siz[ver[i]];} } inline bool check(double x) {for(int i=1;i<=n;i++) d[i]=1.0*w[i]-1.0*x*c[i];for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) dp[i][j]=-2000000000.0;dfs(1,0);for(int i=1;i<=n;i++) if(dp[i][m]>=0) return true;return false; } int main() {//ios::sync_with_stdio(false); cin.tie(0);//freopen(".in","r",stdin);//freopen(".out","w",stdout);n=rd(),m=n-rd();for(int i=1;i<=n;i++) w[i]=rd();for(int i=1;i<=n;i++) c[i]=rd();for(int i=1,x,y;i<n;i++) x=rd(),y=rd(),add(x,y),add(y,x);double nl=0.0,nr=2000000000.0;while(nl+0.001<=nr){double mid=(nl+nr)/2.0;if(check(mid)) ans=mid,nl=mid+0.001;else nr=mid-0.001;}printf("%.1lf\n",ans);//fclose(stdin);//fclose(stdout);return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Binary Search的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。