首页 > 其他分享 >DP--数字三角形模型

DP--数字三角形模型

时间:2023-01-06 21:00:11浏览次数:48  
标签:d% i1 -- scanf i2 int 三角形 include DP

摘花生

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int f[N][N], T, n, m, w[N][N];

int main() 
{
    scanf("%d", &T);
    
    while (T -- ) 
    {
        scanf("%d%d", &n, &m);
        
        for (int i = 1; i <= n; i ++ ) 
            for (int j = 1; j <= m; j ++ ) 
            {
                scanf("%d", &w[i][j]);
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
            }
        printf("%d\n", f[n][m]);
    }
    
    
    return 0;
}

最低通行费

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;
int f[N][N], n, w[N][N];

int main() 
{
    scanf("%d", &n);
    
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= n; j ++ )
            scanf("%d", &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] = min(f[i - 1][j], f[i][j - 1]) + w[i][j];
    
    printf("%d\n", f[n][n]);
    
    return 0;
}

方格取数

#include <iostream>
#include <cstring>

using namespace std;

const int N = 15;
int f[N + N][N][N], n, w[N][N];

int main() 
{
    scanf("%d", &n);
    
    int a, b, c;
    while (scanf("%d%d%d", &a, &b, &c) && a || b) w[a][b] = c;
    
    for (int k = 1; k <= n + n; 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) continue ;
                
                int &x = f[k][i1][i2];
                int t = w[i1][j1];
                if (i1 != i2) t += w[i2][j2];
                
                x = max(x, f[k - 1][i1][i2 - 1] + t);
                x = max(x, f[k - 1][i1][i2] + t);
                x = max(x, f[k - 1][i1 - 1][i2] + t);
                x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
            }
    
    printf("%d\n", f[n + n][n][n]);
    
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100;
int f[N][N][N], n, w[N][N], m;

int main() 
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ ) 
            scanf("%d", &w[i][j]);
    
    for (int k = 1; k <= n + m; k ++ ) 
        for (int i = 1; i < k; i ++ ) 
            for (int j = 1; j < k; j ++ ) 
            {
                int &x = f[k][i][j];
                int t = w[i][k - i];
                if (i != j) t += w[j][k - j];
                
                x = max(x, f[k - 1][i][j - 1] + t);
                x = max(x, f[k - 1][i][j] + t);
                x = max(x, f[k - 1][i - 1][j] + t);
                x = max(x, f[k - 1][i - 1][j - 1] + t);
            }
    
    printf("%d\n", f[n + m][n][n]);
    
    return 0;
}

标签:d%,i1,--,scanf,i2,int,三角形,include,DP
From: https://www.cnblogs.com/StkOvflow/p/17031577.html

相关文章

  • CF1779A Hall of Fame 题解
    可能更好的阅读体验题目传送门题目翻译有\(n\)个纪念碑以及对应的\(n\)个台灯。给定一个由L和R组成的序列\(a\),代表台灯的朝向。如果第\(i\)个台灯为L,代......
  • 稳定性保障6步走:高可用系统大促作战指南!
    转自:稳定性保障6步走:高可用系统大促作战指南!一前言年年有大促,大家对于大促稳定性保障这个词都不陌生,业务场景尽管各不相同,“套路”往往殊路同归,全链路压测、容量评估、......
  • 代码随想录day10 LeetCode 232. 用栈实现队列 225. 用队列实现栈
     232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/利用两个栈来实现队列,一个先存储进去的,一个存储IN栈倒出来的元素,这样就可以获取到队首......
  • 《Quantifying the effects of environment and population diversity in multi-agent
    量化多智能体强化学习中环境和种群多样性的影响总结:在多种实验环境下评估多智能体强化学习受到环境多样性以及智能体多样性的影响,主要是泛化能力实验过程主要是通过改......
  • 技术汇总:第十章:Maven Profile动态选择配置文件
    MavenProfile什么是MavenProfile在我们平常的java开发中,会经常使用到很多配制文件(xxx.properties,xxx.xml),而当我们在本地开发(dev),测试环境测试(test),线上生产使用(product)时,......
  • 道长的算法笔记:状态机模型之股票系列问题
    (一)股票系列问题所谓的股票问题,是一个动态规划状态机模型的系列问题,这些题目来自于LeetCode社区,这些问题非常经典,能够帮助我们理解动态规划的本质,这些问题大多初看之......
  • 【题解】P4027 [NOI2007] 货币兑换
    题意好长,但是不想概括了。\cdq/!思路cdq分治+凸包。首先考虑令\(f_i\)表示第\(i\)天可以得到的最大金额,\(f_1=s\)因为\(rate_i\)是常数,并且保证存在最优方......
  • 与别人交流时如何宣泄情绪
    仅限线上交流把你的情绪表达出来,愤怒不满等等然后带着情绪,给他发语音,接下来注意保持别动转文字OK再删删减减OKOK好了这是一篇既带有我的感情,他又看不出来的消息......
  • 《眩晕》着力唤起眩晕感的电子作品【个人习作】
    作品下载(Windows平台)密码:c0egShader练习作。通过持续地销毁焦点又制造新焦点来使人感到眩晕。场景由5个点光源、约15个Cube搭建而成。模型渲染部分:使用前......
  • 176.第二高的薪水
    题目描述编写一个SQL查询,获取并返回Employee表中第二高的薪水。如果不存在第二高的薪水,查询应该返回null。遇到的难题难题1找到薪资第二高的薪水目前遇到的难......