首页 > 其他分享 >动态规划——数字三角形模型

动态规划——数字三角形模型

时间:2024-08-29 21:03:19浏览次数:11  
标签:动态 int 模型 cin long solve x2 三角形 x1

数字三角形模型

母题 : 数字三角形

32c858b5886d86b8db6d2cc6d133f9f5

思路

​ 集合 f [i] [j] 表示所有从起点走到(i,j)的路径

​ 属性 f [i] [j] 存的数是集合中所有路径和的最大值

​ 状态计算:对于每一条从起点到 ( i , j ) 的路径,其要么是从左上方来的,要么是从右上方来的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n;
int a[510][510];
int f[510][510];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++) cin>>a[i][j];
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++) f[i][j]=-1e9;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];
    int mmax=-1e9;
    for(int i=1;i<=n;i++) mmax=max(mmax,f[n][i]);
    cout<<mmax<<endl; 
    return 0;
}

子题1 : 摘花生

63eb5b0b75f3748d4d2178d4fd9eb7b6

思路

​ 基本和母题的思路一致,转移方程一致

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int f[N][N];
int w[N][N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin>>w[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
    }
    cout<<f[n][m]<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

子题2 : 最低通行费

04e08eef2436637e0b47c3bcf7701441

思路

​ 因为必须在(2*N-1)个单位时间穿越过来,所以只能向右或向左移动

​ 集合 f [i] [j] 表示走到第i行第j列的所有方案

​ 属性 走过路线的总价值最小值Min

​ 转移方程

​ 从左面走过来 从右面走过来

​ f [i] [j] = f [i] [j-1] +w f [i] [j] = f [i-1] [j] +w

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
const int inf = 1e9;
int w[N][N];
int f[N][N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            cin>>w[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==1&&j==1) f[i][j]=w[i][j];
            else
            {
                f[i][j]=inf;
                if(i>1) f[i][j]=min(f[i][j],f[i-1][j]+w[i][j]);
                if(j>1) f[i][j]=min(f[i][j],f[i][j-1]+w[i][j]);
            }
        }
    }
    cout<<f[n][n]<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

子题3 :方格取数

78ab8083b67d851befb40cbe03da79e1

思路

​ 和之前的题不同是本题需要走两边

​ 如果只走一次的话,求从起点到终点的最大权值和应该为:f[i] [j] = max(f[i-1] [j], f[i][j-1])+w[i] [j]; 即f[i][j]表示从起点走到(i,j)的最大权值和,

​ 而本题是从起点走两次走到终点的最大权值和,即状态表示为:f[i1] [j1] [i2] [j2];这里,我们考虑假设两条路线是同时走的,则表示为:所有从起点(1,1)(1,1)出发,然后分别走到(i1,j1),(i2,j2)的最大权值和

​ 我们可以进行 三维优化

​ 状态表示 f [k] [x1] [x2]

​ 集合 同时走K步,所有从(1,1),(1,1)走到 (x1,y1),(x2,y2) 获得花生的数目

​ 属性 Max

​ 状态计算 左 左 f [k-1] [x1-1] [x2-1]

​ 左 上 f [k-1] [x1-1] [x2]

​ 上 左 f [k-1] [x1] [x2-1]

​ 上 上 f [k-1] [x1] [x2]

特判 两个点是否重合 即 x1==x2 如果重合只加w [x1] [j1] 如果不重合加 w [x1] [j1] +w [x2] [j2]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15;
int w[N][N];
int f[N*2][N][N];
void solve()
{
    int n; cin>>n;
    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b]=c;
    for(int k=2;k<=n*2;k++){
        for(int i1=1;i1<=n;i1++){
            for(int i2=1;i2<=n;i2++){
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
                    int t=w[i1][j1];
                    if(i1!=i2) t+=w[i2][j2];
                    int &x=f[k][i1][i2];
                    x=max(x,f[k-1][i1-1][i2-1]+t);
                    x=max(x,f[k-1][i1-1][i2]+t);
                    x=max(x,f[k-1][i1][i2-1]+t);
                    x=max(x,f[k-1][i1][i2]+t);
                }
            }
        }
    }
    cout<<f[n*2][n][n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

子题4 : 传纸条

cbadeb0cc9f4ad2230f4b87f3e5e2ea8

思路

​ 可以思考成和方格取数 相同的代码逻辑,一个从上向下走,一个从下向上走,可以理解为两条路从上向下走,加上其限制条件

​ 状态表示 f [k] [x1] [x2]

​ 集合 同时走K步,所有从(1,1),(1,1)走到 (x1,y1),(x2,y2) 得到权值的最大值

​ 状态计算

​ 左 左 f [k-1] [x1-1] [x2-1]

​ 左 上 f [k-1] [x1-1] [x2]

​ 上 左 f [k-1] [x1] [x2-1]

​ 上 上 f [k-1] [x1] [x2]

注意 不能走到一个格子里 (和方格取数不同的地方) ,因为最优解一定不会相交,一定可以绕开这个点向其他地方走

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=55;
int w[N][N];
int f[N*2][N][N];       //表示两条路径分别到达(i,k-i),(j,k-j);
void solve()
{
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cin>>w[i][j];
    }
    for(int k=2;k<=n+m;k++){
        for(int i=1;i<k;i++){
            for(int j=1;j<k;j++){
                int &v=f[k][i][j];
                int tmp=w[i][k-i];
                if(i!=j) tmp+=w[j][k-j];
                v=max(v,f[k-1][i-1][j]);
                v=max(v,f[k-1][i-1][j-1]);
                v=max(v,f[k-1][i][j-1]);
                v=max(v,f[k-1][i][j]);
                v+=tmp;
            }
        }
    }
    cout<<f[n+m][n][n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

标签:动态,int,模型,cin,long,solve,x2,三角形,x1
From: https://www.cnblogs.com/gloria-wmh/p/18387559

相关文章

  • 五种IO模型的介绍
    前言本文将介绍五种常见的IO模型:阻塞、非阻塞、信号驱动IO、多路复用、异步IO文章的重点在于非阻塞与多路复用。而多路复用IO又有三种常见的方式。后续将会详细介绍。这里就先熟悉一下IO模型、以及认识一下非阻塞IO的编写。建立一个认识IO分为:等+拷贝。比如往磁盘中写数......
  • 2025秋招大语言模型落地实践面试题
    本文系统地从计算力基础设施、软件架构、数据资源、应用场景和脑科学五大核心维度对大模型实践中的问题进行解答。目录计算力基础设施1.1什么是云边端协同架构?1.2信息技术应用创新计划相关政策对企业的影响?软件架构2.1拥有自己的大语言模型(LLM)是否必要?2.2......
  • 关于垂直领域大模型的探索和尝试
    最近这一两周看到不少互联网公司都已经开始秋招提前批面试了。不同以往的是,当前职场环境已不再是那个双向奔赴时代了。求职者在变多,HC在变少,岗位要求还更高了。最近,我们又陆续整理了很多大厂的面试题,帮助一些球友解惑答疑,分享技术面试中的那些弯弯绕绕。总结链接如下:《......
  • AI 大模型在文本生成任务中的创新应用
    目录前言一、文本生成技术的最新进展1.1从规则到深度学习:文本生成技术的演变1.2大型语言模型的崛起:从GPT-3到GPT-41.3创新技术推动文本生成质量提升二、文本生成的创新应用案例分析2.1自动内容创作2.2智能对话系统2.3个性化内容推荐三、高质量文本生成的代......
  • ollama 最快方式部署管理大模型
    github:https://github.com/ollama/ollama模型地址:https://ollama.com/library/llama3.1linux:安装1.下载安装脚本curl-fsSLhttps://ollama.com/install.sh|sh2.修改启动环境变量如果是root用户记得改为rootvim/etc/systemd/system/ollama.service[Unit]Descri......
  • 大模型备案全网最详细流程解读(附附件+重点解读)
    文章目录一、语料安全评估二、黑盒测试三、模型安全措施评估四、性能评估五、性能评估六、安全性评估七、可解释性评估八、法律和合规性评估九、应急管理措施十、材料准备十一、【线下流程】大模型备案线下详细步骤说明十二、【线上流程】算法备案填报流程及重难......
  • 大模型备案全网最详细流程说明【附附件】
    本文要点:大模型备案最详细说明,大模型备案条件有哪些,《算法安全自评估报告》模板,大模型算法备案,大模型上线备案,生成式人工智能(大语言模型)安全评估要点,网信办大模型备案。大模型备案安全评估流程详细说明,见下图:大模型安全评估流程图算法备案安全评估流程详细说明,见下图:算......
  • 大模型备案重难点最详细说明【评估测试题+附件】
    2024年3月1日,我国通过了《生成式人工智能服务安全基本要求》(以下简称《AIGC安全要求》),这是目前我国第一部有关AIGC服务安全性方面的技术性指导文件,对语料安全、模型安全、安全措施、词库/题库要求、安全评估等方面提出了具体规范和要求。(一)适用主体《AIGC安全要求》的适用主......
  • 模型的训练套路
    1.模型训练步骤1.创建网络模型classmyModule(nn.Module):def__init__(self):super(myModule,self).__init__()self.module1=Sequential(Conv2d(3,32,5,padding=2),MaxPool2d(2),Conv2d(32,32,5,......
  • Spark MLlib模型训练—回归算法 Decision tree regression
    SparkMLlib模型训练—回归算法Decisiontreeregression在机器学习中,决策树是一种常用且直观的模型,广泛应用于分类和回归任务。决策树回归(DecisionTreeRegression)通过将数据集分割成多个区域,构建一棵树形结构,以预测目标变量的连续值。本文将详细探讨Spark中的决......