基础动态规划题目基础动态规划题目

news/2024/8/29 1:29:21 标签: 动态规划, 算法, python, c++

目录

题目1： P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

 代码示例：

题目2： Common Subsequence

代码示例

题目3 ：最长上升子序列

最长不下降子序列

最长上升子序列oj答案

题目1： P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P1216

 代码示例：

// c++ 代码示例
#include <algorithm>
#include <iostream>

using namespace std ;

int n,a[1005][1005],f[1005][1005] ;

int dfs(int x, int y)
{
    if (x == n) return a[x][y] ;
    if (f[x][y] != -1) return f[x][y] ;
    return f[x][y] = max(dfs(x + 1, y), dfs(x + 1, y + 1)) + a[x][y] ;
}

int main()
{
    int n ;
    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++)
        {
            f[i][j] = -1 ;
        }
    }
    cout << dfs(1, 1) ;
    return 0 ;
}
// c++ 代码示例

#include <algorithm>
#include <iostream>
using namespace std ;

long long n, a[1005][1005] ;
int main()
{
    cin >> n ;
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = 1 ; j <= i ; j++)
        {
            cin >> a[i][j] ;
        }
    }
    for (int i = n ; i >= 1 ; i--)
    {
        for (int j = 1 ; j <= i ; j++)
        {
            a[i][j] = a[i][j] + max(a[i + 1][j], a[i + 1][j + 1]);        
            
        }
    }
    cout << a[1][1] ;
    return 0 ;
    
}

 

// c++ 代码示例

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;

#define rint register int
inline void read(int &x)
{
    x = 0;
    int w = 1;
    char ch = getchar();
    while (!isdigit(ch) && ch != '-')
    {
        ch = getchar();
    }
    if (ch == '-')
    {
        w = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ '0');
        ch = getchar();
    }
    x = x * w;
}

const int maxn = 1000 + 10;

int n, a[maxn][maxn], ans;

int main()
{
    read(n);
    for (rint i = 1; i <= n; i++)
    {
        for (rint j = 1; j <= i; j++)
        {
            read(a[i][j]);
            if (i == 1 && j == 1)
            {
                // The top of the triangle
                continue;
            }
            if (j == 1)
            {
                // Left boundary
                a[i][j] += a[i - 1][j];
            }
            else if (j == i)
            {
                // Right boundary
                a[i][j] += a[i - 1][j - 1];
            }
            else
            {
                // Middle elements
                a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
            }
            ans = max(ans, a[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}

题目2： Common Subsequence

Common Subsequence - HDU 1159 - Virtual Judge (vjudge.net)icon-default.png?t=N7T8https://vjudge.net/problem/HDU-1159

代码示例

// c++ 代码示例
int a[MAXN], b[MAXN], f[MAXN][MAXN] ;

int dp()
{
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = 1 ; j <= m ; j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                f[i][j] = f[i - 1][j - 1] + 1 ;
            }
            else
            {
                f[i][j] = std::max(f[i - 1][j], f[i][j - 1]) ;
            }
        }
    }
    return f[n][m] ;
}
// c++ 代码示例

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
char a[1001], b[1001];
int dp[1001][1001], len1, len2;
 
void lcs(int i,int j)
{
    for(i=1; i<=len1; i++)
    {
        for(j=1; j<=len2; j++)
        {
            if(a[i-1] == b[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else if(dp[i-1][j] > dp[i][j-1])
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = dp[i][j-1];
        }
    }
}
 
int main()
{
    while(~scanf(" %s",a))
    {
        scanf(" %s", b);
        memset(dp, 0, sizeof(dp));
        len1 = strlen(a);
        len2 = strlen(b);
        lcs(len1, len2);
        printf("%d\n", dp[len1][len2]);
    }
    return 0;
}

题目3 ：最长上升子序列

信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)icon-default.png?t=N7T8http://ybt.ssoier.cn:8088/problem_show.php?pid=1281

最长不下降子序列

//c++代码示例
# include <iostream>
# include <cstdio>
using namespace std ;
int n ;
int a[1001] ;
int f[1001] ;
int mx = -1 ;
int main()
{
    scanf("%d", &n) ;
    for (int i = 1 ; i <= n ; i++)
    {
        scanf("%d", &a[i]) ;
        f[i] = 1 ;
    }
    for (int i = 2 ; i <= n ; i++)
    {
        for (int j = i - 1 ; j >= 1 ; j--)
        {
            if (a[i] >= a[j])
            {
                f[i] = max(f[i], f[j] + 1) ;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++)
    {
        mx = max(mx, f[i]) ;
    }
    printf("%d", mx) ;
    return 0 ;
    
}
//c++代码示例
# include <iostream>
# include <cstdio>
using namespace std ;
int n ;
int a[1001] ;
int f[1001] ;
int mx = -1 ;
int main()
{
    scanf("%d", &n) ;
    for (int i = 1 ; i <= n ; i++)
    {
        scanf("%d", &a[i]) ;
        f[i] = 1 ;
    }
    for (int i = n - 1 ; i >= 1 ; i--)
    {
        for (int j = i + 1 ; j <= n ; j++)
        {
            if (a[i] <= a[j])
            {
                f[i] = max(f[i], f[j] + 1) ;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++)
    {
        mx = max(mx, f[i]) ;
    }
    printf("%d", mx) ;
    return 0 ;
    
}

最长上升子序列oj答案

//c++代码示例
# include <iostream>
# include <cstdio>
using namespace std ;
int n ;
int a[1001] ;
int f[1001] ;
int mx = -1 ;
int main()
{
    scanf("%d", &n) ;
    for (int i = 1 ; i <= n ; i++)
    {
        scanf("%d", &a[i]) ;
        f[i] = 1 ;
    }
    for (int i = n - 1 ; i >= 1 ; i--)
    {
        for (int j = i + 1 ; j <= n ; j++)
        {
            if (a[i] < a[j])
            {
                f[i] = max(f[i], f[j] + 1) ;
            }
        }
    }
    for (int i = 1 ; i <= n ; i++)
    {
        mx = max(mx, f[i]) ;
    }
    printf("%d", mx) ;
    return 0 ;
    
}

http://www.niftyadmin.cn/n/5559850.html

相关文章

day05：微信登录、商品浏览

day05：微信登录、商品浏览

文章目录 HttpClient介绍入门案例 微信小程序开发介绍准备工作注册小程序完善小程序信息下载开发者工具 入门案例了解小程序目录结构编写小程序代码编译小程序 微信登录微信登录流程需求和分析代码开发 HttpClient 介绍 HttpClient是Apache的一个子项目&#xff0c;是高效的、…
阅读更多...
C语言——指针简介及基本要点

C语言——指针简介及基本要点

C语言中的指针是C语言的核心特性之一&#xff0c;它允许程序员直接访问内存地址。指针变量存储的是变量的内存地址&#xff0c;而不是变量的值。通过指针&#xff0c;程序可以更加灵活地操作内存中的数据&#xff0c;进行数据的动态分配和访问。下面是一些关于C语言指针的基本概…
阅读更多...
2024年中级消防设施操作员（考前冲刺）证考试题库及中级消防设施操作员（考前冲刺）试题解析

2024年中级消防设施操作员（考前冲刺）证考试题库及中级消防设施操作员（考前冲刺）试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年中级消防设施操作员&#xff08;考前冲刺&#xff09;证考试题库及中级消防设施操作员&#xff08;考前冲刺&#xff09;试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作…
阅读更多...
redis其他类型和配置文件

redis其他类型和配置文件

很多博客只讲了五大基本类型&#xff0c;确实&#xff0c;是最常用的&#xff0c;而且百分之九十的程序员对于Redis只限于了解String这种最常用的。但是我个人认为&#xff0c;既然Redis官方提供了其他的数据类型&#xff0c;肯定是有相应的考量的&#xff0c;在某些特殊的业务…
阅读更多...
【深度学习入门篇 ⑤ 】PyTorch网络模型创建

【深度学习入门篇 ⑤ 】PyTorch网络模型创建

【&#x1f34a;易编橙&#xff1a;一个帮助编程小伙伴少走弯路的终身成长社群&#x1f34a;】 大家好&#xff0c;我是小森( &#xfe61;ˆoˆ&#xfe61; ) &#xff01; 易编橙终身成长社群创始团队嘉宾&#xff0c;橙似锦计划领衔成员、阿里云专家博主、腾讯云内容共创官…
阅读更多...
i18n、L10n、G11N 和 T9N 的含义

i18n、L10n、G11N 和 T9N 的含义

注&#xff1a;机翻&#xff0c;未校对。 Looking into localization for the first time can be terrifying, if only due to all of the abbreviations. But the meaning of i18n, L10n, G11N, and T9N, are all very easy to understand. 第一次研究本地化可能会很可怕&…
阅读更多...
C语言内存管理深度解析面试题及参考答案（2万字长文)

C语言内存管理深度解析面试题及参考答案（2万字长文)

在嵌入式面试时，C语言内存管理是必问面试题，也是难点，相关知识点可以参考： C语言内存管理深度解析​​​​​​​ 下面整理了各种类型的C语言内存管理的面试题： 目录 全局变量和局部变量在内存中分别存储在哪个区域？ 静态变量和全局变量有什么区别？ 什么是作用域？…
阅读更多...
Qt实现MDI应用程序

Qt实现MDI应用程序

本文记录Qt实现MDI应用程序的相关操作实现 目录 1.MDM模式下窗口的显示两种模式 1.1TabbedView 页签化显示 1.2 SubWindowView 子窗体显示 堆叠cascadeSubWindows 平铺tileSubWindows 2.MDM模式实现记录 2.1. 窗体继承自QMainWindow 2.2.增加组件MdiArea 2.3.定义统一…
阅读更多...
最新文章

Copyright @ 2022~2023