本文共 1250 字，大约阅读时间需要 4 分钟。
要求比值最大，当然用分数规划。
二分答案，转化为选取一个最大的联通块使得它们的和大于0
然后我们直接DP。
复杂度$O(n^2\log {n})$
#include #include #include #include #include #include #include using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long#define inf 1e15#define eps 1e-6#define mp make_pair#define maxn 2505int k,n;double s[maxn],p[maxn],l,r,mid,dp[maxn][maxn],tmp[maxn];int h[maxn],to[maxn],ne[maxn],en=0,siz[maxn]; void add(int a,int b){to[en]=b;ne[en]=h[a];h[a]=en++;} void Tree_DP(int o){ dp[o][1]=p[o]-mid*s[o];siz[o]=1; for (int i=h[o];i>=0;i=ne[i]) { Tree_DP(to[i]); F(j,0,siz[o]+siz[to[i]]) tmp[j]=-inf; F(j,1,siz[o]) F(k,0,siz[to[i]]) tmp[j+k]=max(tmp[j+k],dp[o][j]+dp[to[i]][k]); F(j,0,siz[o]+siz[to[i]]) dp[o][j]=max(dp[o][j],tmp[j]); siz[o]+=siz[to[i]]; }} int main(){ memset(h,-1,sizeof h); scanf("%d%d",&k,&n);k++; F(i,1,n) { int x; scanf("%lf%lf%d",&s[i],&p[i],&x); add(x,i); } l=0;r=1e10; while (fabs(r-l)>eps) { mid=(l+r)/2; F(i,0,n) F(j,0,k) dp[i][j]=-inf; s[0]=1;p[0]=mid; Tree_DP(0); int flag=0; if (dp[0][k]>=0) l=mid; else r=mid; } printf("%.3f\n",l);}
转载于:https://www.cnblogs.com/SfailSth/p/6736890.html