当前位置： 首页 > article >正文

C++动态规划-线性DP

article 2025/8/14 22:19:22

这是一套C++线性DP题目的答案。如果需要题目，请私信我，我将会更新题干

P1:单子序列最大和

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[200005];
int s[200005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){int tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}int ans=INT_MIN;for(int i=1; i<=n; i++){s[i]=max(s[i-1]+a[i],a[i]);ans=max(ans,s[i]);}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[200005];
int s[200005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        int tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
    int ans=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        s[i]=max(s[i-1]+a[i],a[i]);
        ans=max(ans,s[i]);
    }
    cout<<ans;
    return 0;
}
P2 跳格子

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){int tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}
//	for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//	cout<<'\n';int ans=INT_MIN;for(int i=1; i<=n; i++){s[i]=max(s[i-1],s[i-2])+a[i-1];}cout<<s[n];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        int tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
//    for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//    cout<<'\n';
    int ans=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        s[i]=max(s[i-1],s[i-2])+a[i-1];
    }
    cout<<s[n];
    return 0;
}
跳格子2

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){int tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}
//	for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//	cout<<'\n';for(int i=1; i<=n; i++) s[i]=min(s[i-1],s[i-2])+a[i];cout<<s[n];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,A,B,C;
int a[100005];
int s[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        int tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
//    for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//    cout<<'\n';
    for(int i=1; i<=n; i++) s[i]=min(s[i-1],s[i-2])+a[i];
    cout<<s[n];
    return 0;
}
[动态规划]数塔

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105][105];
int s[105][105];
int main()
{ios::sync_with_stdio(0);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=1; i<=n; i++){for(int j=1; j<=i; j++) s[i][j]=max(s[i-1][j],s[i-1][j-1])+a[i][j];}int ans=INT_MIN;for(int i=1; i<=n; i++) ans=max(s[n][i],ans);cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105][105];
int s[105][105];
int main()
{
    ios::sync_with_stdio(0);
    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=1; i<=n; i++)
    {
        for(int j=1; j<=i; j++) s[i][j]=max(s[i-1][j],s[i-1][j-1])+a[i][j];
    }
    int ans=INT_MIN;
    for(int i=1; i<=n; i++) ans=max(s[n][i],ans);
    cout<<ans;
    return 0;
}
方格取数1

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
long long s[105][105];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=0; i<=n+1; i++){for(int j=0; j<=m+1; j++) s[i][j]=INT_MAX;}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) cin>>a[i][j];}s[1][1]=a[1][1];for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(!(i==1&&j==1)) s[i][j]=min(s[i-1][j],s[i][j-1])+a[i][j];}}/*for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) cout<<setw(2)<<s[i][j]<<" ";cout<<'\n';}*/cout<<s[n][m];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[105][105];
long long s[105][105];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0; i<=n+1; i++)
    {
        for(int j=0; j<=m+1; j++) s[i][j]=INT_MAX;
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++) cin>>a[i][j];
    }
    s[1][1]=a[1][1];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            if(!(i==1&&j==1)) s[i][j]=min(s[i-1][j],s[i][j-1])+a[i][j];
        }
    }
    /*
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++) cout<<setw(2)<<s[i][j]<<" ";
        cout<<'\n';
    }
    */
    cout<<s[n][m];
    return 0;
}
take

#include <bits/stdc++.h>
using namespace std;
int n;
int a[55],s[55];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1; i<=n; i++) cin>>a[i];int ans=INT_MIN;for(int i=1; i<=n; i++){s[i]=INT_MIN;for(int j=2; j<=i; j++) s[i]=max(s[i-j]+a[i],s[i]);if(i==1) s[i]=a[i];ans=max(ans,s[i]);//cout<<s[i]<<" ";}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[55],s[55];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    int ans=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        s[i]=INT_MIN;
        for(int j=2; j<=i; j++) s[i]=max(s[i-j]+a[i],s[i]);
        if(i==1) s[i]=a[i];
        ans=max(ans,s[i]);
        //cout<<s[i]<<" ";
    }
    cout<<ans;
    return 0;
}
大盗阿福（开long long）

#include <bits/stdc++.h>
using namespace std;
int n,x,y,z;
long long a[100005];
long long s[100005];
long long b[100005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>x>>y>>z;for(int i=1; i<=n; i++) a[i]=((long long)i*i*x+i*y+z)%1000+1;long long ans=LONG_LONG_MIN;
//	for(int i=1; i<=n; i++) cin>>a[i];
//	cout<<'\n';for(int i=1; i<=n; i++){s[i]=b[i-2]+a[i];if(s[i]>ans) ans=s[i];if(s[i]>b[i-1]) b[i]=s[i];else b[i]=b[i-1];//cout<<s[i]<<" ";}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,x,y,z;
long long a[100005];
long long s[100005];
long long b[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>x>>y>>z;
    for(int i=1; i<=n; i++) a[i]=((long long)i*i*x+i*y+z)%1000+1;
    long long ans=LONG_LONG_MIN;
//    for(int i=1; i<=n; i++) cin>>a[i];
//    cout<<'\n';
    for(int i=1; i<=n; i++)
    {
        s[i]=b[i-2]+a[i];
        if(s[i]>ans) ans=s[i];
        if(s[i]>b[i-1]) b[i]=s[i];
        else b[i]=b[i-1];
        //cout<<s[i]<<" ";
    }
    cout<<ans;
    return 0;
}
Leapcow

#include <bits/stdc++.h>
using namespace std;
int n,e,b;
bool g[40005];
int s[40005];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>e>>n>>b;for(int i=1; i<=b; i++){int x;cin>>x;g[x]=1;}for(int i=1; i<=e; i++){s[i]=INT_MAX;for(int j=max(0,i-n); j<=i; j++){if(g[j]==1) continue;s[i]=min(s[i],s[j]+1);}}cout<<s[e];return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,e,b;
bool g[40005];
int s[40005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>e>>n>>b;
    for(int i=1; i<=b; i++)
    {
        int x;
        cin>>x;
        g[x]=1;
    }
    for(int i=1; i<=e; i++)
    {
        s[i]=INT_MAX;
        for(int j=max(0,i-n); j<=i; j++)
        {
            if(g[j]==1) continue;
            s[i]=min(s[i],s[j]+1);
        }
    }
    cout<<s[e];
    return 0;
}
乘车费用

#include <bits/stdc++.h>
using namespace std;
long long a[15];
long long s[105];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(int i=1; i<=10; i++) cin>>a[i];int n;cin>>n;for(int i=1; i<=n; i++){if(!s[i]) s[i]=LONG_LONG_MAX;for(int j=1; j<=10; j++){int now=s[i-j]+a[j];if(s[i]>now) s[i]=now;}}cout<<s[n];return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long a[15];
long long s[105];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=1; i<=10; i++) cin>>a[i];
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        if(!s[i]) s[i]=LONG_LONG_MAX;
        for(int j=1; j<=10; j++)
        {
            int now=s[i-j]+a[j];
            if(s[i]>now) s[i]=now;
        }
    }
    cout<<s[n];
    return 0;
}
双子序列最大和

#include <bits/stdc++.h>
using namespace std;
int a[1005];
int ps[1005];
int ls[1005],rs[1005];
int main()
{/*1.生成 2.前缀和3.1~n左序列（正常生成）4.n~1右序列（正常生成）5.1~n-1左右序列匹配 图 . . . . .---   ---左    右 */int n,A,B,C;cin>>n>>A>>B>>C;for(int i=1; i<=n; i++){ls[i]=INT_MIN;rs[i]=INT_MIN;long long tmp=((long long)A*i*i+B*i+C)%20000;a[i]=tmp-10000;}for(int i=1; i<=n; i++) ps[i]=ps[i-1]+a[i];int nm=0;int maxf=INT_MIN;for(int i=1; i<=n; i++){nm=max(a[i],nm+a[i]);maxf=max(maxf,nm);ls[i]=maxf;}nm=0;maxf=INT_MIN;for(int i=n; i>=1; i--){nm=max(a[i],nm+a[i]);maxf=max(maxf,nm);rs[i]=maxf;}int ans=INT_MIN;for(int i=1; i<n; i++){if(i+2<=n) ans=max(ans,ls[i]+rs[i+2]);}cout<<ans;return 0;
}

#include <bits/stdc++.h>
using namespace std;
int a[1005];
int ps[1005];
int ls[1005],rs[1005];
int main()
{
    /*
    1.生成 
    2.前缀和
    3.1~n左序列（正常生成）
    4.n~1右序列（正常生成）
    5.1~n-1左右序列匹配 
    图 
    . . . . .
    ---   ---
    左    右 
    */
    int n,A,B,C;
    cin>>n>>A>>B>>C;
    for(int i=1; i<=n; i++)
    {
        ls[i]=INT_MIN;
        rs[i]=INT_MIN;
        long long tmp=((long long)A*i*i+B*i+C)%20000;
        a[i]=tmp-10000;
    }
    for(int i=1; i<=n; i++) ps[i]=ps[i-1]+a[i];
    int nm=0;
    int maxf=INT_MIN;
    for(int i=1; i<=n; i++)
    {
        nm=max(a[i],nm+a[i]);
        maxf=max(maxf,nm);
        ls[i]=maxf;
    }
    nm=0;
    maxf=INT_MIN;
    for(int i=n; i>=1; i--)
    {
        nm=max(a[i],nm+a[i]);
        maxf=max(maxf,nm);
        rs[i]=maxf;
    }
    int ans=INT_MIN;
    for(int i=1; i<n; i++)
    {
        if(i+2<=n) ans=max(ans,ls[i]+rs[i+2]);
    }
    cout<<ans;
    return 0;
}

http://www.lryc.cn/news/2404600.html

相关文章：

  • Java高级 | 【实验七】Springboot 过滤器和拦截器
  • es地理信息索引的类型以及geo_point‌和geo_hash的关系
  • 深入理解 Spring IOC：从概念到实践
  • Vue解决开发环境 Ajax 跨域问题
  • 行为设计模式之Command （命令）
  • 若依添加添加监听容器配置（删除键，键过期）
  • NeRF 技术深度解析：原理、局限与前沿应用探索(AI+3D 产品经理笔记 S2E04)
  • ROS2，工作空间中新建了一个python脚本，需要之后作为节点运行。告诉我步骤？
  • 【AI智能体】Spring AI MCP 从使用到操作实战详解
  • Vue:Ajax
  • 法律大语言模型（Legal LLM）技术架构
  • 理解 RAG_HYBRID_BM25_WEIGHT：打造更智能的混合检索增强生成系统
  • Hive终极性能优化指南：从原理到实战
  • 第六十二节：深度学习-加载 TensorFlow/PyTorch/Caffe 模型
  • MobaXterm配置跳转登录堡垒机
  • 零基础在实践中学习网络安全-皮卡丘靶场（第八期-Unsafe Filedownload模块）
  • 测试 FreeSWITCH 的 mod_loopback
  • 【C++快读快写】
  • 测试（面经 八股）
  • [面试精选] 0104. 二叉树的最大深度
  • 图上合成：用于大型语言模型持续预训练的知识合成数据生成
  • MYSQL(二) ---MySQL 8.4 新特性与变量变更
  • 数学复习笔记 27
  • 现代简约壁炉：藏在极简线条里的温暖魔法
  • 限流算法java实现
  • 机器学习×第二卷：概念下篇——她不再只是模仿，而是开始决定怎么靠近你
  • Linux 下关于 ioremap 系列接口
  • 常用函数库之 - std::function
  • php执行系统命令的四个常用函数
  • 力扣-17.电话号码的字母组合