题目：给出n个a和b，让选出n-k个使得最大 。

二分法（二分一个mid看是否存在这样的一组解，不断缩小区间逼近最优值）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define eps 1e-6
#define inf 1e12
const int maxn=1010;
int n,k;
int a[maxn],b[maxn];
double y[maxn];
bool check(double x)
{
    for(int i=1;i<=n;i++)
        y[i]=a[i]-b[i]*x;
    sort(y+1,y+n+1);
    double sum=0;
    for(int i=1;i<=k;i++)
        sum+=y[n-i+1];
    return sum>0;
}

void solve()
{
    double l=0,r=inf;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        if(check(mid))
            l=mid;
        else r=mid;
    }
    printf("%.0f\n",l*100.0);
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(n+k==0) break;
        k=n-k;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        solve();
    }
    return 0;
}


Dinkelbach算法 （本质是一种迭代算法，基于这样的思想：不去二分答案，而是先随便给定一个答案，然后根据更优的解不断移动答案，逼近最优解。理论上它比二分快些。 在这个算法中，一般将ans初始化为0）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define eps 1e-6
#define inf 1e12
const int maxn=1010;
struct node{
    int a,b;
    double y;
}s[maxn];
bool cmp(const node &a,const node &b)
{
    return a.y>b.y;
}
int n,k;
double Dinkelbach()
{
    double ans=0,x=0,U,D;
    while(1)
    {
        x=ans;
        for(int i=1;i<=n;i++)
            s[i].y=s[i].a-s[i].b*x;
        sort(s+1,s+n+1,cmp);
        U=D=0;
        for(int i=1;i<=k;i++)
        {
            U+=1.0*s[i].a;
            D+=1.0*s[i].b;
        }
        ans=U/D;
        if(fabs(ans-x)<eps)
            return ans;
    }
}

int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        if(n+k==0) break;
        k=n-k;
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i].a);
        for(int i=1;i<=n;i++)
            scanf("%d",&s[i].b);
        printf("%.0f\n",Dinkelbach()*100.0);
    }
    return 0;
}


 

求解的大问题是在区间[1, n]内合并石子的最优值，石子分成两个区间[1,k][k+1,n]。不断地将大区间分成小区间。
设dpmax[i][j]表示i堆石子到j堆石子合并得到的最大分数，dpmin[i][j]表示i堆石子到j堆石子合并得到的大小分数，num[i][j]表示i堆石子到j堆石子的总数
状态转移方程：

dpmax[i][j]=max{dp[i][k]+dp[k+1][j]+num[i][j]} k在区间[i, j-1]内

dpmin[i][j]=min{dp[i][k]+dp[k+1][j]+num[i][j]} k在区间[i, j-1]内

3.初始化：dpmax[i][i]=0;dpmin[i][j]=0;就是说一堆石子没办法和相邻的石子合并

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define clr(x) memset(x,0,sizeof(x))
#define INF 0x1f1f1f1f
long long fmax[105][105];
long long fmin[105][105];
long long a[105];
long long sum[105];
long long num[105][105];
int n,i,j,len,k;
int main(){
    while(scanf("%d",&n)!=EOF){
        clr(sum);
        clr(fmax);
        memset(fmin,INF,sizeof(fmin));
        int tot=0;
        for(i=1;i<=n;i++){
           scanf("%lld",&a[i]);
           tot=tot+a[i];
           sum[i]=tot;
        }
        for(i=1;i<=n;i++)
        for(j=i;j<=n;j++){
            num[i][j]=sum[j]-sum[i-1];
        }
        //f[i][j]=f[i+k]+f[k+1][j]+num[i][j]
        for(i=1;i<=n;i++)
        fmin[i][i]=0,fmax[i][i]=0;
        for(len=1;len<n;len++){
            for(i=1;i<=n-len;i++){
                j=i+len;
                for(k=i;k<j;k++){
                    fmax[i][j]=max(fmax[i][j],fmax[i][k]+fmax[k+1][j]+num[i][j]);
                    fmin[i][j]=min(fmin[i][j],fmin[i][k]+fmin[k+1][j]+num[i][j]);
                }
            }
        }
        printf("%lld %lld\n",fmin[1][n],fmax[1][n]);
    }
    return 0;
}

首先放上原题链接
点我，点我进入原题


什么是动态规划？
在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。而且每次求出的解不是独立的，我们需要逐层推出最优解。

以这道题为例，题目要求整棵二叉树加分最大，并且分数=左子树分数* 右子树分数+自身数值，这就需要使左右子树分数尽可能大->左右子树的子树要大，所以我们就需要选取一个合适的根节点。并且求出此时的最大分数。
求解过程
接着就是求解动态规划的状态转移方程了。

我们其实就可以将题目看做求[i,j]这个区间里的最大值，这样就可以得出状态转移方程
f[i][j]=max{f[i][k-1]*f[k+1][j]+f[k][k]  |  i<=k<=j}//i,j是区间范围，k为根节点

题目还要求先序遍历输出，所以我们还需要一个root[i][j]数组来表示节点i到节点j成树的最大加分所选的根节点。
下面上代码进行分析
#include <iostream>
using namespace std;
long long n;
long long f[100][100],root[100][100];//创建所需要的f和root数组
void xianxu(long long ,long long );//先序遍历的函数
int main()
{
	int i,len,j;
	cin>>n;
	for(i=1;i<=n;i++)//因为中序遍历从1开始的，所以从1开始有很好的对应性
	{
		cin>>f[i][i];//将分数值存储到相应的f里
		root[i][i]=i;//中序的遍历的数据
	}
	for(len=1;len<n;len++)
	{
		for(i=1;i+len<=n;i++)//多次取范围，求取符合f[i][k-1]*f[k+1][j]+f[k][k]最大的情况
		{
			j=i+len;//范围的右边界
			f[i][j]=f[i+1][j]+f[i][i];//易知当有左子树时，不会是最优解，所以最大值先先赋值为根+右子树的分数
			root[i][j]=i;//默认设置根为第一个值
			for(int k=i+1;k<j;k++)//当根为第二个，第三个……直到范围边界
			{
				if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])//计算当前取的根的情况下，f[i][j]是否为当前的最大值
				{
					f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];//如果是，f[i][j]里的最大值就赋值
					root[i][j]=k;//记录取最大值时的根
				}
			}
		}
	}
	cout<<f[1][n]<<endl;//输出题目要求的[1,n]的最大值
	xianxu(1,n);//进行先序遍历
	return 0;
}
void xianxu(long long l,long long r)
{
	if(l>r)//当左边比右边大时，进行回溯
	{
		return;
	}
	cout<<root[l][r]<<" ";//输出先序遍历输出
	if(l==r)//左右相等时回溯
	{
		return;
	}
	xianxu(l,root[l][r]-1);//遍历左子树
	xianxu(root[l][r]+1,r);//遍历右子树
}


至此完结

题目：

我是超链接

题解：

首先平均数最大，平均数其实是${\sum a\over \sum 1}$，求最值是01分数规划的问题 

二分mid，如果有更优的值$\sum (a-mid)>0$，那么我们的check途径就是通过点分治判断长度在[l,r]区间内有没有一条链的和>0，链的长度为a[i]-mid

而check的过程中对于每个当前子树，维护每个深度的最优值，我们只需要取之前记录的最优的一项更新就好了。我们可以把当前子树中的值按深度从大到小来更新答案，这个过程中使用单调队列维护一个深度下降权值序列，然后每次取队首更新答案即可，每次查看队首的时候把已经相加超过R的踢出去，然后查看队尾，如果比这次要添加的L-j（即下限）更小的话就T出去

这个过程是线性的，而对于全部子树 i 深度最长距离的数组的更新也只是取个max，它也是线性的。$O(nlog^2n)$

这题已经调的我不想写题解了，只能说ljBZOJ

代码：



#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=150005;
#define INF 1e9
int tot,nxt[N*2],L,R,point[N],v[N*2],f[N],size[N],root,sum,deep[N],DEP,dep,q[N];
double c[N*2],a[N],b[N],mid,ans;bool vis[N];
int read()
{
    char ch=getchar();int x=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x;
}
void addline(int x,int y,double z)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z; 
}
void getroot(int x,int fa)
{
    f[x]=0; size[x]=1;
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa && !vis[v[i]])
      {
        getroot(v[i],x);
        size[x]+=size[v[i]];
        f[x]=max(f[x],size[v[i]]);
      }
    f[x]=max(f[x],sum-size[x]);
    if (f[x]<f[root]) root=x;
}
void getdeep(int x,int fa)
{
    deep[x]=deep[fa]+1;
    for (int i=point[x];i;i=nxt[i])
      if (v[i]!=fa && !vis[v[i]]) getdeep(v[i],x);
    DEP=max(DEP,deep[x]);
}
void dfs(int x,int fa,double sum)
{
    if (deep[x]>R) return;
    a[deep[x]]=max(a[deep[x]],sum);
    for (int i=point[x];i;i=nxt[i])
      if (!vis[v[i]] && v[i]!=fa) dfs(v[i],x,sum+c[i]-mid);
    dep=max(dep,deep[x]);
}
bool check()
{
    double maxx=-INF;int now=0;
    b[0]=0;
    for (int i=1;i<=DEP;i++) b[i]=-INF;
    for (int i=point[root];i;i=nxt[i])
      if (!vis[v[i]])
      {
        int l=1,r=0;dep=0;a[0]=0;
        for (int j=1;j<=DEP;j++) a[j]=-INF;
        dfs(v[i],root,c[i]-mid);

        if (now) q[++r]=now;
        for (int j=1;j<=dep;j++)
        {
            if (j>R) break;
            while (l<=r && q[l]+j>R) l++;
            if (j<=L && L-j<=DEP)
            {
                while (l<=r && b[q[r]]<b[L-j]) r--;
                q[++r]=L-j;
                maxx=max(maxx,b[q[l]]+a[j]);
            }else if (j>L) maxx=max(maxx,b[q[l]]+a[j]); 
        }
        for (int j=1;j<=dep;j++)
        {
            b[j]=max(b[j],a[j]);
            if (j>=L && j<=R && b[now]<b[j]) now=j;
        }
      }
    return maxx>0;
}
void work()
{
    DEP=0;////
    getdeep(root,0);
    double l=ans,r=1e6;
    while (r-l>1e-4)
    {
        mid=(l+r)/2;
        if (check()) l=mid;else r=mid;
    }
    vis[root]=1;ans=l;
    for (int i=point[root];i;i=nxt[i])
      if (!vis[v[i]])
      {
        sum=size[v[i]]; if (sum<L) continue;
        root=0; f[0]=INF; getroot(v[i],0);
        work();
      }
}
int main()
{
    int n;n=read();L=read();R=read(); 
    for (int i=1;i<n;i++) 
    {
        int x,y,z;x=read();y=read();z=read();
        addline(x,y,z);
    }
    deep[0]=-1;
    sum=n; root=0; f[0]=INF; getroot(1,0);
    work();
    printf("%.3lf",ans);
}