首页 > 其他分享 >DAG上的DP

DAG上的DP

时间:2024-07-03 21:42:01浏览次数:16  
标签:DAG int long DP && data1 dp data2

DAG是有向无环图
而DAG的dp主要是利用一些问题的二元关系构造DAG图建模,转化成在图上求最长/短路的问题

https://www.luogu.com.cn/problem/UVA437

Code

点击查看代码
#include <bits/stdc++.h>
using namespace std;
// typedef long long ll;
#define int long long
typedef unsigned long long ull;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define req(i, n, a) for (int i = n; i >= a; i--)
typedef pair<int, int> pa;
int mod        = 998244353;
const int MAXN = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int n, x[40], y[40], z[40];
int dp[40][4];
//dp[i][j]是在以第i个砖为底,j式的所能堆塔的最大高度
int dfs(int k, int f) {
    //dp最大的dp[k][f]
    if (dp[k][f]) return dp[k][f];
    int data1, data2;
    if (f == 1) data1 = y[k], data2 = z[k];
    if (f == 2) data1 = x[k], data2 = z[k];
    if (f == 3) data1 = x[k], data2 = y[k];
    for (int i = 1; i <= n; i++) {
        if ((data1 > y[i] && data2 > z[i]) || (data2 > y[i] && data1 > z[i])) {
            dp[k][f] = max(dp[k][f], dfs(i, 1) + x[i]);
        }
        if ((data1 > x[i] && data2 > z[i]) || (data2 > x[i] && data1 > z[i])) {
            dp[k][f] = max(dp[k][f], dfs(i, 2) + y[i]);
        }
        if ((data1 > x[i] && data2 > y[i]) || (data2 > x[i] && data1 > y[i])) {
            dp[k][f] = max(dp[k][f], dfs(i, 3) + z[i]);
        }
    }
    return dp[k][f];
}

void solve() {
    int cnt = 0;
    while (++cnt) {
        cin >> n;
        if (!n) break;
        for (int i = 1; i <= n; i++) {
            cin >> x[i] >> y[i] >> z[i];
        }
        int high = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            high = max(high, dfs(i, 1) + x[i]);
            high = max(high, dfs(i, 2) + y[i]);
            high = max(high, dfs(i, 3) + z[i]);
        }
        cout << "Case " << cnt << ": maximum height = " << high << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int TT = 1;
    // cin >> T;
    while (TT--) {
        solve();
    }
#ifdef local
    std::cout << endl, system("pause");
#endif
    return 0;
}
// cout << fixed << setprecision(2) <<
// priority_queue<pa, vector<pa>, greater<pa>>qx;
// priority_queue<int, vector<int>, less<int>>qd;
// struct node {
//     int id, f;
//     bool operator<(const node& x) const { return id > x.id; }
// };priority_queue<node> q;

标签:DAG,int,long,DP,&&,data1,dp,data2
From: https://www.cnblogs.com/uanQ/p/18282604

相关文章

  • AT_dp_y Grid 2 题解
    题目传送门前置知识计数DP|排列组合解法正难则反,考虑求出总方案数和至少经过一个黑色格子的方案数,二者作差即为所求。强制增加一个黑色格子\((h,w)\),使得存在一条至少经过一个黑色格子的路径。如果没有“不能移动到黑色格子中”的限制,那么就是一个简单的格路计数问题,方......
  • 基于GWO灰狼优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下(完整代码运行后无水印):     2.算法涉及理论知识概要       LDPC码是一种线性错误修正码,以其接近香农极限的优良性能而被广泛应用于现代通信系统中。NMS译码是一种基于最小平方误差准则的软判决译码方法,其目标是找到一......
  • 有向无环图DAG
     有向无环图(DirectedAcyclicGraphs),简称为DAG.  用于SAT相关文献——查询DirectedAcyclicGraphsSAT结果Neng-FaZhou, RuiweiWang, RolandH.C.Yap:AComparisonof SAT Encodingsfor Acyclicityof Directed Graphs. SAT 2023: 30:1-30:9......
  • CF 1981 D. World is Mine (*1800) DP+博弈论
    CF1981D.WorldisMine(*1800)DP+博弈论题目链接题意:有\(n\)个蛋糕,每个蛋糕有一个美味值\(a_i\),\(Alice\)和\(Bob\)轮流吃蛋糕,\(Alice\)每次必须选择吃严格大于之前所吃的蛋糕美味程度。\(Bob\)随意选择。有人没有蛋糕可以吃时,游戏结束。\(Alice\)想吃更多......
  • python编写使用xmlrpc上传wordpress网站文章的程序
    1、安装库        pipinstallpython-wordpress-xmlrpc,tkinter,xmlrpc,json2、发布文章url="http://域名/xmlrpc.php"username=用户名password=密码title=标题content=内容tags=标签categories=分类client=C......
  • Profibus DP主站转Modbus网关连接伺服与电机通讯
    ProfibusDP主站转Modbus网关连接伺服与电机通讯在工业自动化领域,将ProfibusDP主站转Modbus网关(XD-MDPBM20)用于连接伺服与电机通讯是一种常见且重要的应用方式。当使用ProfibusDP主站转Modbus网关(XD-MDPBM20)连接伺服与电机进行通讯时,可以参考以下步骤进行配置和操作:1.什么是Pro......
  • DDPM扩散概率模型数学原理推导
    DDPM正向过程定义前向过程被定义为一个从初始数据x0x_0x0​开始的马尔可夫链。而他的目标是要由......
  • WordPress付费进群V2主题,多种引流方法,引私域二次变现
    全新前端UI界面,多种前端交互特效让页面不再单调,进群页面群成员数,群成员头像名称,每次刷新页面随机更新不重复,最下面评论和点赞也是如此随机刷新不重复进群页面简介,群聊名称,群内展示,常见问题后台一键开关方便控制,付费进群系统后台自定义你的内容,底部显示你所设置的进群金额,也......
  • AT_tdpc_number 数 题解
    题目传送门前置知识数位DP|记忆化搜索解法本题的提交在luogu上挂了,建议去原站或Vjudge上提交。基础数位DP,记录当前位置、已填的数码之和,接着记忆化搜索即可。需要注意的是\(0\bmodd=0\),如果写得不太好看(未处理前导零)的话需要减去其贡献。代码#include<bits/......
  • Profibus DP主站转Modbus网关连接智能化电表通讯
    ProfibusDP主站转Modbus网关(XD-MDPBM20),是实现不同工业通信协议之间互联互通的设备,主要将ProfibusDP协议转换为Modbus协议,实现数据的双向传输。通过ProfibusDP主站转Modbus网关(XD-MDPBM20),可以有效实现现场设备和控制系统之间的无缝连接,提高生产效率。ProfibusDP主站转Modbus网......