wing是什么_分段计价的数学题

wing是什么_分段计价的数学题给定一个由 n 行数字组成的数字梯形如下图所示。梯形的第一行有 m 个数字。从梯形的顶部的 m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。规则 1:从梯形的顶至底的 m 条路径互不相交。规则 2:从梯形的顶至底的 m 条路径仅在数字结点处相交。规则 3:从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。对于给定的数字梯形,分别按照规则 1,规则 2,和规则 3 计算出从梯形的顶至底的 m 条路径,使这 m 条路径经过的数字总和最大。输入格式第 1

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一个由 n 行数字组成的数字梯形如下图所示。

梯形的第一行有 m 个数字。

从梯形的顶部的 m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

规则 1:从梯形的顶至底的 m 条路径互不相交。

规则 2:从梯形的顶至底的 m 条路径仅在数字结点处相交。

规则 3:从梯形的顶至底的 m 条路径允许在数字结点相交或边相交。
在这里插入图片描述

对于给定的数字梯形,分别按照规则 1,规则 2,和规则 3 计算出从梯形的顶至底的 m 条路径,使这 m 条路径经过的数字总和最大。

输入格式
第 1 行中有 2 个正整数 m 和 n,分别表示数字梯形的第一行有 m 个数字,共有 n 行。

接下来的 n 行是数字梯形中各行的数字。第 1 行有 m 个数字,第 2 行有 m+1 个数字,以此类推。

输出格式
将按照规则 1,规则 2,和规则 3 计算出的最大数字总和输出,每行输出一个最大总和。

数据范围
1≤n,m≤20,
梯形中的数字范围 [1,1000]。

输入样例:
2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1
输出样例:
66
75
77
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1200, M = 4000, INF = 1e8;

int m, n, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
int id[40][40], cost[40][40];

void add(int a, int b, int c, int d)
{ 
   
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx ++ ;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx ++ ;
}

bool spfa()
{ 
   
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    { 
   
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        { 
   
            int ver = e[i];
            if (f[i] && d[ver] < d[t] + w[i])
            { 
   
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver])
                { 
   
                    q[tt ++ ] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}

int EK()
{ 
   
    int cost = 0;
    while (spfa())
    { 
   
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1])
        { 
   
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

int main()
{ 
   
    int cnt = 0;
    scanf("%d%d", &m, &n);
    S = ++ cnt;
    T = ++ cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        { 
   
            scanf("%d", &cost[i][j]);
            id[i][j] = ++ cnt;
        }

    // 规则1
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        { 
   
            add(id[i][j] * 2, id[i][j] * 2 + 1, 1, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, 1, 0);
            if (i < n)
            { 
   
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
            }
        }
    printf("%d\n", EK());

    // 规则2
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        { 
   
            add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
            if (i < n)
            { 
   
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
            }
        }
    printf("%d\n", EK());

    // 规则3
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
        { 
   
            add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
            if (i < n)
            { 
   
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0);
            }
        }
    printf("%d\n", EK());

    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169074.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • gdb调试命令的使用及总结_大锅安装调试指南

    gdb调试命令的使用及总结_大锅安装调试指南写这篇文档的目的是对前面GDB的知识做一次总览,本文为GDB调试指南,参考GDB调试手册,目前已有的篇目:启动调试断点设置查看源码单步调试查看变量前言GDB是Linux下非常好用且强大的调试工具。GDB可以调试C、C++、Go、java、objective-c、PHP等语言。对于一名Linux下工作的c/c++程序员,GDB是必不可少的工具,本篇以C语言来调试。GDB简介U…

    2022年10月24日
  • 新秀nginx源代码分析数据结构篇(四)红黑树ngx_rbtree_t

    新秀nginx源代码分析数据结构篇(四)红黑树ngx_rbtree_t

  • js获取request中的值_set协议工作原理

    js获取request中的值_set协议工作原理设置http请求头HttpURLConnection.setRequestProperty(Stringkey,Stringvalue); 这个我居然都忘记了,哎~真是岁数大了,心好累。。。 例如:下面就是一个完整的原始网络请求方式HttpURLConnectionconn=null;try{…

  • windows彻底删除idea

    windows彻底删除idea1程序卸载打开控制面板,选中idea,卸载;2注册表清理每个程序安装后都会有注册码,必须删除;windows+R然后输入regedit:进入注册表,2.1点击一级菜单HKEY_CURRENT_USER,右键查找,输入idea,会找到jetbrains,然后,右键删除。2.2再来一次,点击一级菜单HKEY_CURRENT_USER,右键查找,输入jetbrain,会找到jetbrain相关,然后,右键删除。3卸载残留清理主要有几个地方C:\\ProgramF

  • 传感器开发流程!_传感器工艺流程

    传感器开发流程!_传感器工艺流程今天公司要求我进行传感器的开发,而且只给2天时间,反映下自己没做过这方面可能需要时间延长下,不管,就给你两天时间!干不完就使劲加班…现在企业压榨劳动力太赤裸裸了

  • 全国各地DNS地址详细列表

    全国各地DNS地址详细列表北京DNS地址:202.96.199.133、202.96.0.133、202.106.0.20、202.106.148.1、202.97.16.195、202.106.196.115上海DNS地址:202.96.199.132、202.96.199.133、202.96.209.5、202.96.209.6、202.96.209.133天津DNS地址:202.99.9…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号