精华内容
下载资源
问答
  • 二分法(二分一个mid看是否存在这样一组解,不断缩小区间逼近最值) #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> ...

    题目:给出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堆石子合并得到...

    求解的大问题是在区间[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);//遍历右子树
    }
    

    在这里插入图片描述

    至此完结

    展开全文
  • 二分mid,如果有更优的值∑(a−mid)&gt;0∑(a−mid)&gt;0\sum (a-mid)>0,那么我们的check途径就是通过点分治判断长度在[l,r]区间内有没有一条链的和&gt;0,链的长度为a[i]-mid 而check的过程中...

    题目:

    我是超链接

    题解:

    首先平均数最大,平均数其实是a1,求最值是01分数规划的问题
    二分mid,如果有更优的值(amid)>0,那么我们的check途径就是通过点分治判断长度在[l,r]区间内有没有一条链的和>0,链的长度为a[i]-mid

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

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

    这题已经调的我不想写题解了,只能说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);
    }
    展开全文
  • 一根树枝有N段,每一段有一个分数,可以选取一些不完全包含(可以相交)的区间,每次选取可以得到区间里所有数之和的分数。求最大得分。 解题过程: 1.很明显的dp,默认选取区间的顺序是从左往右,F[i][j]表示...
  • 比如要为学生的成绩按照分数线分为、良、中、及格、和不及格,对应的分数线如下: 等级 良 中 及格 不及格 分数区间 90-100 80-89 70-79 60-69 0-59 分数在该区间的概率 10% 30% 40% 10% 10% 现在...
  • NC数学考试JAVA实现

    2020-05-22 13:20:16
    题目 分析 通过前缀和来求取区间分数和,从左到又枚举区间,答案及当前区间与之前最大...因为如果之后有更优的区间选择的话,枚举到后面这个区间时会更新答案,避免重复计算。 代码 import java.util.Scanner; publi
  • Matlab程序设计

    千次阅读 2014-06-22 14:55:03
    1.switch-case-end结构 function grade_assess(Name,Score) %此函数用来评定学生成绩 %Name,Score为参数,需要用户输入 %Name中元素为学生姓名 ...%将分数区间划开:(85~100),良(70~84),及格(60~69
  • poj 1390 Blocks

    2015-01-19 00:08:28
    黑书上例题,类似区间dp一般是dp[i][j]表示区间状态(i,j)能取到值,这题用dp[i][j][k],这个k看似与最值没啥关系。。仔细一想却很巧妙,他假设之后会有k个与第j段颜色相同方块一起消,这样在后面某段...
  • uva 10559——Blocks

    2015-12-18 20:04:47
    题意:有n个带颜色的方块,同种颜色的方块连成一个区域,每次可以消除一个区域的方块x,然后得到分数x2,右边的方块左移,然后问求最大的分数。 思路:区间dp,dp(i,j,k)表示区间(i,j)在右边添上k个颜色...
  • R语言Wald检验 vs 似然比检验

    千次阅读 2019-09-04 15:25:18
    在这篇文章中,我将修改Wald和似然比检验的优缺点。我将重点关注置信区间而不是检验 。 示例 我们将X表示观察到成功次数随机变量,x表示其实现值。似然函数只是二项式概率函数,但参数是模型参数。所以ML....
  • \(dp[i][j]\) 表示处理完 \([i...j]\) 最大分数 然后你会发现这种方法连样例1都不能搞定 因为 \(dp[i][j]\) 可能受到后面一些同色块影响,导致直接处理不能获得最值 那怎么办? 哪有问题就解决哪里 添加一位 \...
  • 然后发现这道题需要支持区间更改和单点查询操作,所以首先想到是异或意义下分数组,于是自己便写了一个差分数组,确实好写,但很慢(可能我写),下面是五十分异或意义下差分代码: 1 #...
  • bzoj3316 jc loves mkk 二分&单调队列

    千次阅读 2015-12-22 21:43:47
    这道题目居然还要狗血的分数输出,真是卡精度,果断long double。  首先破环成链,然后二分答案x,用每一项减去x,那么如果有L~R的区间内且和大于0的这么一段存在,记录一下区间返回1就行了。  如何判断呢?其实...
  • 洛谷P3957 跳房子

    2018-05-15 21:19:51
    发现答案可行区间是单调,所以二分答案,容易推出f[i]表示到达第i个格子最大值,枚举上一步跳了多少来转移 然后仔细观察可以发现对于一个状态,如果有比他后面状态比他答案大话,显然不会..于是可以....
  • BZOJ 4476送礼物

    2018-11-05 21:17:03
    题目大意:一个整数序列n,给定一个长度范围...首先这个答案肯定是单调,我们可以二分答案,把求最问题转化为判定性问题。那么我们只差一个check函数。我们二分一个mid,如果不考虑区间长度在L到R之内话,...
  • 可以私聊QQ1457785526

    2020-12-15 20:57:22
    你只需要在原数组中根据优秀与合格的分数线,按德、才双优,德,德胜才,合格的,其它的顺序(同一种情况按总分从高到低排列)进行就地分类重排,输入由测试程序...
  • 包括Libsvm、Liblinear包选择,分词,词典生成,特征选择,SVM参数,SVM模型训练等都可以一步完成。 利用生成模型对未知文本做预测。并返回预测标签以及该类隶属度分数。可自动识别libsvm和...
  • 想知道北邮各个组过院线人数、分数分布?(请查阅 2. 初试成绩排名) 想知道北邮各学院各组复试名单、每个组原报与调剂情况?(请查阅3. 复试名单) 想知道北邮各学院各组差额复试比、录取情况、复试刷人...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

优的分数区间