精华内容
下载资源
问答
  • 最小成本排序:两个数交换,这两个数相加,一组数全部交换成有序之后,累加和就是成本。 如何求出最小的成本,有一点难度,主要在于有两种情况的分析,一种是每个元素交换到正确位置(会形成一些闭合的圆),进行...

    最小成本排序:两个数交换,这两个数相加,一组数全部交换成有序之后,累加和就是成本。

    如何求出最小的成本,有一点难度,主要在于有两种情况的分析,一种是每个元素交换到正确位置(会形成一些闭合的圆),进行计算;另外一种是需要在圆外借元素(最小的那个元素),这样的成本才是最小的。所以求最小的成本就是两种情况最小的即可!

    公式1:\sum A[i]+(n-2)*min(A[i]) 

    公式2:\sum A[i] + min(A[i]) +(n+1)*x   (其中x就是输入的最小数)

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    static const int MAX=1000;
    static const int VMAX=10000;
    
    int n,A[MAX],B[MAX],T[VMAX+1];
    int x;//整个输入最小的元素
    
    int solve()
    {
        int MinCost=0;//最小成本
        bool flag[MAX];
        for(int i=0; i<n; i++){
            B[i]=A[i];
            flag[i]=false;
        }
        sort(B,B+n);//升序排列(默认)
        for(int i=0;i<n;i++){T[B[i]]=i;}//保存元素所在的正确位置
        for(int i=0;i<n;i++){
            if(flag[i]){continue;}
            int cur=i;
            int S=0;//求和
            int m=VMAX;//每个圆内最小的元素
            int an=0;//每个圆内元素的个数
            while(1){
                flag[cur]=true;
                an++;
                int v=A[cur];//圆内的数值
                S+=v;//求和
                m=min(m,v);
                cur=T[v];//圆内数值所在索引值
                if(flag[cur]){break;}//遍历完一个圆圈,跳出
            }
            //MinCost+=S+(an-2)*m;
            //MinCost+=S+m+(an+1)*x;
            MinCost+=min(S+(an-2)*m,S+m+(an+1)*x);//计算“不借元素”和“借最小元素”两种情况,取成本小的一方
        }
        return MinCost;
    }
    int main()
    {
        cout<<"数组长度:";
        cin>>n;
        x=VMAX;
        for(int i=0;i<n;i++){
            cin>>A[i];
            x=min(x,A[i]);
        }
        int result=solve();
        cout<<result;
        return 0;
    }
    

    展开全文
  • hdu4289(最小割)

    2015-02-17 17:48:00
    传送门:Control ...分析:根据割的定义将整部图分成两部分且互不相通,这题明显是求最小割,根据最小割等于最大流,则拆点后直接求最大流即可,对于点值在最大流中的限制经常是拆点处理。 #pragma comm...

     

    传送门:Control

    题意:有n个城市,有个小偷想从其中一个城市逃到另一个城市,警察想要堵截这个小偷,知道了在每个城市堵截的成本,问如何安排在哪些城市堵截可以使得小偷一定会被抓住,而且成本最低。

    分析:根据割的定义将整部图分成两部分且互不相通,这题明显是求最小割,根据最小割等于最大流,则拆点后直接求最大流即可,对于点值在最大流中的限制经常是拆点处理。

    #pragma comment(linker,"/STACK:1024000000,1024000000")
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cmath>
    #include <limits.h>
    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <cstdlib>
    #include <stack>
    #include <vector>
    #include <set>
    #include <map>
    #define LL long long
    #define mod 100000000
    #define inf 0x3f3f3f3f
    #define eps 1e-6
    #define N 100010
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define PII pair<int,int>
    using namespace std;
    inline int read()
    {
        char ch=getchar();
        int x=0,f=1;
        while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
        while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    int n,m,vs,vt,tot,NV;
    int head[N],gap[N],level[N],q[N];
    struct edge
    {
        int v,w,next;
        edge(){}
        edge(int v,int w,int next):v(v),w(w),next(next){}
    }e[N<<1];
    void addedge(int u,int v,int w)
    {
        e[tot]=edge(v,w,head[u]);
        head[u]=tot++;
        e[tot]=edge(u,0,head[v]);
        head[v]=tot++;
    }
    void init()
    {
        memset(head,-1,sizeof(head));
        tot=0;
    }
    /***************************SAP***********************/
    void bfs(int vt)
    {
        memset(level,-1,sizeof(level));
        memset(gap,0,sizeof(gap));
        level[vt]=0;
        gap[level[vt]]++;
        queue<int>que;
        que.push(vt);
        while(!que.empty()) {
            int u=que.front();
            que.pop();
            for(int i=head[u]; i!=-1; i=e[i].next) {
                int v=e[i].v;
                if(level[v]!=-1)continue;
                level[v]=level[u]+1;
                gap[level[v]]++;
                que.push(v);
    
            }
        }
    }
    int pre[N];
    int cur[N];
    int SAP()
    {
        bfs(vt);
        memset(pre,-1,sizeof(pre));
        memcpy(cur,head,sizeof(head));
        int u=pre[vs]=vs,flow=0,aug=inf;
        gap[0]=NV;
        while(level[vs]<NV) {
            bool flag=false;
            for(int &i=cur[u]; i!=-1; i=e[i].next) {
                int v=e[i].v;
                if(e[i].w&&level[u]==level[v]+1) {
                    flag=true;
                    pre[v]=u;
                    u=v;
                    aug=min(aug,e[i].w);
                    if(v==vt) {
                        flow+=aug;
                        for(u=pre[v]; v!=vs; v=u,u=pre[u]) {
                            e[cur[u]].w-=aug;
                            e[cur[u]^1].w+=aug;
                        }
                        aug=inf;
                    }
                    break;
                }
            }
            if(flag)continue;
            int minlevel=NV;
            for(int i=head[u]; i!=-1; i=e[i].next) {
                int v=e[i].v;
                if(e[i].w&&level[v]<minlevel) {
                    minlevel=level[v];
                    cur[u]=i;
                }
            }
            if(--gap[level[u]]==0)break;
            level[u]=minlevel+1;
            gap[level[u]]++;
            u=pre[u];
        }
        return flow;
    }
    /**************************SAP**********************/
    int x,y;
    void build()
    {
        vs=read();vt=read()+n;NV=2*n+1;
        for(int i=1;i<=n;i++)
        {
            x=read();
            addedge(i,i+n,x);
            addedge(i+n,i,x);
        }
        for(int i=1;i<=m;i++)
        {
            x=read();y=read();
            addedge(x+n,y,inf);
            addedge(y+n,x,inf);
        }
    }
    int main()
    {
        while(scanf("%d%d",&n,&m)>0)
        {
            init();
            build();
            printf("%d\n",SAP());
        }
    }
    View Code

     

    转载于:https://www.cnblogs.com/lienus/p/4295366.html

    展开全文
  • 1 描述 问题:修建一个连接各个小区与煤气供应站点之间的管道,使得造价...对下图所示图,用Prim算法求最小生成树。 流程如上图,还可以用表格形式​​​​​ 3Kruskal算法实例 反复在满足如下条件的边中...

    1 描述

    问题修建一个连接各个小区与煤气供应站点之间的管道,使得造价成本最低,即构造一颗最小生成树。但是如何求解?

    对应模型:树结构,生成树,最小生成树

    prim算法实例

    基本思想:在满足如下条件的边中选出一条最小的边:

                    一端已选,另一端未选。

            因此,该算法需要给出起点,以作为已选顶点。

    对下图所示图,用Prim算法求最小生成树。

    流程如上图,还可以用表格形式​​​​​

     3 Kruskal算法实例

    反复在满足如下条件的边中选出一条最小的边——和已选边不构成回路。

    判断构成回路的经典方法:电位法

        初始状态:各顶点的电位=顶点号

        每当选择一条边时,相连通的顶点的电位全都按照其中最小的值设置。

        由此可知新的候选边是否和已选边构成回路

    Kruskal算法的时空复杂度为O(eloge)、O(n^3) 。其时间性能和空间性能都不是很如意。

     

     

     

     

     

     

     

    展开全文
  • 机器人如何移动使得总成本最小 题目分析 将这N个点按位置排序 显然如果一个点走过他再回头修一定不会最优 所以任意时刻已修补的区间一定是连续的 即若当前以修好第llllll~rrrrrr个地点,那么下一个修补的一定是ll...

    UVA1336 Fixing the Great Wall

    Time limit 3000ms
    在这里插入图片描述


    题目大意

    长城上有N个地点要修补,给定每个点的位置、初始修复成本,每单位时间增加的成本
    给定修补机器人 初始位置及移动速度
    求机器人如何移动使得总成本最小


    题目分析

    将这N个点按位置排序
    显然如果一个点走过他再回头修一定不会最优
    所以任意时刻已修补的区间一定是连续的
    即若当前以修好第llll~rrrr个地点,那么下一个修补的一定是ll1ll-1rr+1rr+1

    定义dp[ll][rr][0/1]dp[ll][rr][0/1]表示已经修好了[ll,rr][ll,rr]区间的地点,且当前所在位置为ll(0)ll(0)还是rr(1)rr(1)
    修补完剩下的地点所需最小化费

    初始化dp[1][n][0]=dp[1][n][1]=0dp[1][n][0]=dp[1][n][1]=0,其余为INF
    状态转移方程
    W=Sum[n](Sum[rr]Sum[ll1])W=Sum[n]-(Sum[rr]-Sum[ll-1])及计算剩余没修补的地点每单位时间增加的成本总和
    dp[ll][rr][0]=min(dp[ll1][rr][0]+Len(ll1,ll)/VW,dp[ll][rr+1][1]+Len(ll,r+1)/VW)dp[ll][rr][0]=min(dp[ll-1][rr][0]+Len(ll-1,ll)/V*W,dp[ll][rr+1][1]+Len(ll,r+1)/V*W)
    dp[ll][rr][1]=min(dp[ll1][rr][0]+Len(ll1,rr)/VW,dp[ll][rr+1][1]+Len(rr,r+1)/VW)dp[ll][rr][1]=min(dp[ll-1][rr][0]+Len(ll-1,rr)/V*W,dp[ll][rr+1][1]+Len(rr,r+1)/V*W)

    注意这里我们还要把机器人的初始位置作为一个点加进去,所以总点数应为N+1
    设排序后表示机器人的点为K,从DP(k,k,0)开始记搜即可
    答案为dp[k][k][0]+SUMdp[k][k][0]+SUM (SUM为初始成本总和)


    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    typedef double dd;
    
    int read()
    {
        int f=1,x=0;
        char ss=getchar();
        while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
        while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
        return f*x;
    }
    
    const int inf=1e9;
    const int maxn=1010;
    int n,v,x;
    struct node{dd pos,c,dt;}rem[maxn];
    bool cmp(node a,node b){return a.pos<b.pos;}
    dd sum[maxn],dp[maxn][maxn][2];
    
    dd DP(int ll,int rr,int d)
    {
        if(ll==1&&rr==n+1) return 0;
        if(dp[ll][rr][d]!=inf) return dp[ll][rr][d];
        dd resl=0,resr=0,ss=sum[n+1]-(sum[rr]-sum[ll-1]);
        if(ll>1){
            if(d==1) resl=(rem[rr].pos-rem[ll-1].pos)/v*ss;
            else resl=(rem[ll].pos-rem[ll-1].pos)/v*ss;
        }
        if(rr<=n){
            if(d==1) resr=(rem[rr+1].pos-rem[rr].pos)/v*ss;
            else resr=(rem[rr+1].pos-rem[ll].pos)/v*ss;
        }
        if(ll>1) dp[ll][rr][d]=min(dp[ll][rr][d],DP(ll-1,rr,0)+resl);
        if(rr<=n) dp[ll][rr][d]=min(dp[ll][rr][d],DP(ll,rr+1,1)+resr);
        return dp[ll][rr][d];
    }
    
    int main()
    {
        while(scanf("%d%d%d",&n,&v,&x)!=EOF)
        {
        	if(n==0&&v==0&&x==0) break; dd ssum=0;
        	for(int i=1;i<=n;++i)
        	scanf("%lf%lf%lf",&rem[i].pos,&rem[i].c,&rem[i].dt);
        	rem[n+1].pos=x; rem[n+1].c=0; rem[n+1].dt=0;//将机器人也作为一个点加入
        
        	sort(rem+1,rem+2+n,cmp);
        	for(int i=1;i<=n+1;++i)
        	ssum+=rem[i].c,
            sum[i]=sum[i-1]+rem[i].dt;
        	
        	for(int i=1;i<=n+1;++i)
        	for(int j=1;j<=n+1;++j)
        	dp[i][j][0]=dp[i][j][1]=inf;
        	
        	for(int i=1;i<=n+1;++i)
        	if(rem[i].pos==x){ printf("%.0lf\n",floor(DP(i,i,0)+ssum)); break;}
        }
        return 0;
    }
    
    

    洛谷P2466 [SDOI2008]Sue的小球

    时空限制 1000ms / 128MB

    题目描述

    Sue和Sandy最近迷上了一个电脑游戏,这个游戏的故事发在美丽神秘并且充满刺激的大海上,Sue有一支轻便小巧的小船。然而,Sue的目标并不是当一个海盗,而是要收集空中漂浮的彩蛋,Sue有一个秘密武器,只要她将小船划到一个彩蛋的正下方,然后使用秘密武器便可以在瞬间收集到这个彩蛋。然而,彩蛋有一个魅力值,这个魅力值会随着彩蛋在空中降落的时间而降低,Sue要想得到更多的分数,必须尽量在魅力值高的时候收集这个彩蛋,而如果一个彩蛋掉入海中,它的魅力值将会变成一个负数,但这并不影响Sue的兴趣,因为每一个彩蛋都是不同的,Sue希望收集到所有的彩蛋。

    然而Sandy就没有Sue那么浪漫了,Sandy希望得到尽可能多的分数,为了解决这个问题,他先将这个游戏抽象成了如下模型:

    以Sue的初始位置所在水平面作为x轴。

    一开始空中有N个彩蛋,对于第i个彩蛋,他的初始位置用整数坐标(xi, yi)表示,游戏开始后,它匀速沿y轴负方向下落,速度为vi单位距离/单位时间。Sue的初始位置为(x0, 0),Sue可以沿x轴的正方向或负方向移动,Sue的移动速度是1单位距离/单位时间,使用秘密武器得到一个彩蛋是瞬间的,得分为当前彩蛋的y坐标的千分之一。

    现在,Sue和Sandy请你来帮忙,为了满足Sue和Sandy各自的目标,你决定在收集到所有彩蛋的基础上,得到的分数最高。

    输入格式:

    第一行为两个整数N, x0用一个空格分隔,表示彩蛋个数与Sue的初始位置。
    第二行为N个整数xi,每两个数用一个空格分隔,第i个数表示第i个彩蛋的初始横坐标。
    第三行为N个整数yi,每两个数用一个空格分隔,第i个数表示第i个彩蛋的初始纵坐标。
    第四行为N个整数vi,每两个数用一个空格分隔,第i个数表示第i个彩蛋匀速沿y轴负方向下落的的速度。

    输出格式:

    一个实数,保留三位小数,为收集所有彩蛋的基础上,可以得到最高的分数。

    说明

    对于30%的数据,N<=20。
    对于60%的数据,N<=100。
    对于100%的数据,104&lt;=xi,yi,vi&lt;=104N&lt;=1000-10^4 &lt;= xi,yi,vi &lt;= 10^4,N &lt; = 1000


    题目分析

    和上面一样的题型
    每个彩蛋ii的得分看作 初始从坐标yiy_i-下落距离
    为了让这个得分尽可能的大,转换一下就是要让下落距离尽量小

    令SUM为初始所有纵坐标总和sum[i]sum[i]记录viv_i前缀和
    dp[ll][rr][0/1]dp[ll][rr][0/1]表示已经取得了第llll~rrrr的彩蛋且当前在llll还是rrrr,要取完剩下区间能得到的最小下落距离

    和上面的转移如出一辙
    记得把初始位置也作为一个点加进去xixi升序排序后记搜即可
    最后ans=(SUMDP(K,K,0))/1000ans=(SUM-DP(K,K,0))/1000


    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<set>
    #include<cmath>
    using namespace std;
    typedef long long lt;
    typedef double dd;
    
    int read()
    {
        int x=0,f=1;
        char ss=getchar();
        while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
        while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
        return x*f;
    }
    
    const int inf=1128481603;
    const int maxn=1010;
    int n,x0,SUM;
    struct node{ int xi,yi,vi,f; node(){xi=yi=vi=f=0;}}rem[maxn];
    bool cmp(node a,node b){return a.xi<b.xi;}
    int sum[maxn],dp[maxn][maxn][2];
    
    int DP(int ll,int rr,int d)
    {
    	if(ll==1&&rr==n) return 0;
    	if(dp[ll][rr][d]!=inf) return dp[ll][rr][d];
    	int res=inf,resl=0,resr=0,ss=sum[n]-(sum[rr]-sum[ll-1]);
    	if(ll>1){
    		if(d==1) resl=(rem[rr].xi-rem[ll-1].xi)*ss;
    		else resl=(rem[ll].xi-rem[ll-1].xi)*ss;
    	}
    	if(rr<n){
    		if(d==1) resr=(rem[rr+1].xi-rem[rr].xi)*ss;
    		else resr=(rem[rr+1].xi-rem[ll].xi)*ss;	
    	}
    	if(ll>1) res=min(res,resl+DP(ll-1,rr,0));
    	if(rr<n) res=min(res,resr+DP(ll,rr+1,1));
    	return dp[ll][rr][d]=res;
    }
    
    int main()
    {
        n=read(); x0=read();
        for(int i=1;i<=n;++i) rem[i].xi=read();
        for(int i=1;i<=n;++i) rem[i].yi=read();
        for(int i=1;i<=n;++i) rem[i].vi=read();
        rem[++n].xi=x0; rem[n].yi=0; rem[n].vi=0; rem[n].f=1;
        
        memset(dp,67,sizeof(dp));
    	sort(rem+1,rem+n+1,cmp);
        for(int i=1;i<=n;++i) 
    	sum[i]=sum[i-1]+rem[i].vi,SUM+=rem[i].yi;
    	
        for(int i=1;i<=n;++i)
        if(rem[i].f==1){ printf("%.3lf",(dd)(SUM-DP(i,i,1))/1000.0); break;}
        return 0;
    }
    
    
    展开全文
  • 如果当前状态到最终状态的最小成本h加上当前状态深度超过了限制深度d,就可以直接中断搜索。 问题链接ALDS1_13_C:15 Puzzle问题内容 当前16宫格如何移动成目标的16宫格。 思路 用A*或者IDA* 算法实现 代码IDA*...
  • 随着物流行业的兴盛,如何用最短的时间,最节约成本的方案,完成送货任务显得尤为重要.针对本案例,我们采用了大量的科学分析方法,并进行了多次反复验证,得出如下结果: 1:根据所给问题及有关数据,我们将题目中...
  • 22、 对于上图给出的有向图,写出最小成本生成树,给出求解算法。 动态规划 23、 出上图中每对结点间的最短距离的算法,并给出计算结果。 24、 下图中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的...
  • 7 4 单位时间成本最小比率环 92 7 5 旅行推销员问题 93 第 8 章 最短路径 94 8 1 组合的属性 94 8 2 权重为 0 或 1 的图 96 8 3 权重为正值或空值的图: Dijkstra 算法 97 8 4 随机权重的图:Bellman-Ford 算法 100 ...
  • 图片加载不出来如何解决? https://github.com/fe-lucifer/fanqiang 《91 天学算法》限时活动 很多教育机构宣传的 7 天,一个月搞定算法面试的,我大概都了解了下,不怎么靠谱。学习算法这东西,还是要考积累,没有...
  • 19.简述在最小工作模式下,8086如何响应一个总线请求? 答:外部总线主控模块经HOLD引线向8086发出总线请求信号;8086在每个时钟周期的上升沿采样HOLD引线;若发现HOLD=1则在当前总线周期结束时(T4结束)发出总线...
  • 本书作者将16年的教练经验与积累撰写成本系列丛书,全面、深入而系统地将ACM-ICPC展现给读者。本系列丛书包括《ACM国际大学生程序设计竞赛:知识与入门》、《ACM国际大学生程序设计竞赛:算法与实现》、《ACM国际...
  • 自动打印机

    2012-01-03 14:03:02
    4)自动打印机系统采用一个电机驱动主轴控制三个机构的执行构件完成各自的功能运动,如何将三个执行机构的主动件均固定在主轴上而达到设计要求是需要认真考虑的。 1.4 设计任务 (1) 按工艺动作要求拟定运动循环图...
  • 大话数据结构

    2018-12-14 16:02:18
    100个人的高考成绩平均分与全省所有考生的成绩平均分在占用时间和内存存储上有非常大的差异,我们自然追求高效率和低存储的算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高...
  • 例如,经济学的许多重要推论(包括利润最大化要求边际收入等于边际成本这样一个著名的微观经济学定理在内)都导源于微分学的最佳化过程。正是因为这些相互关系的大量存在,我们才在上面说,管理经济学各种定义的差别...
  • 从PL/SQL编程、PL/SQL程序结构、PL/SQL程序数据、PL/SQL中的SQL、PL/SQL应用构建、高级PL/SQL主题这6个方面详细系统地讨论了PL/SQL以及如何有效地使用它。《Oracle PL/SQL程序设计(第5版)(套装上下册)》能够帮助...
  • 31、EJB包括(SessionBean,EntityBean)说出他们的生命周期,及如何管理事务的?  SessionBean: Stateless Session Bean 的生命周期是由容器决定的,当客户机发出请求要建立一个Bean的实例时,EJB容器不一定要创建...
  • java 面试题 总结

    2009-09-16 08:45:34
    round方法返回与参数最接近的长整数,参数加1/2后其floor. 27、String s = new String("xyz");创建了几个String Object? 两个 28、设计4个线程,其中两个线程每次对j增加1,另外两个线程对j每次减少1。写出程序...
  • 6.3.4 支持网络的复制如何工作 238 6.4 恢复目录管理 239 6.4.1 合并恢复目录 239 6.4.2 移动恢复目录到另一个数据库 241 6.4.3 虚拟专用目录 242 6.5 增强的RMAN与Data Guard的集成 246 6.5.1 不用数据库...

空空如也

空空如也

1 2
收藏数 28
精华内容 11
关键字:

如何求最小成本