C. Minimum Grid Path (贪心)

矫情吗；* 2021-07-17 00:56 320阅读 0赞

[题目][Link 1]

思路：贪心的想如果要使花费尽量小，那就让第一第二小的线段一个向上一个向右尽可能长，只需枚举即可。但是由于有一个每次需要转弯的限制，所以需要分为奇偶，分别记录奇偶前面最小的cost，让奇数的线段向上，偶数的线段向右，先将其余线段长度全部取为1，然后让剩下的长度分别由向上和向右的最小cost线段走完即可，细节见代码。

Code:

#include<iostream>
    #include<cmath>
    #include<map>
    typedef long long ll;
    using namespace std;
    const int Max = 1e6 + 5;
    ll ji[Max], o[Max], sum[Max];
    
    int main()
    { 
    	int t;cin >> t;
    	while (t--)
    	{ 
    		int n;cin >> n;
    		ll ans = 1e18;
    		ji[0] = 1e18, o[0] = 1e18;
    		for (int i = 1;i <= n;i++)
    		{ 
    			ll a;cin >> a;
    			sum[i] = sum[i - 1] + a;
    			ji[i] = ji[i - 1], o[i] = o[i - 1];
    			if (i % 2 == 1)ji[i] = min(a, ji[i - 1]);
    			else o[i] = min(o[i - 1], a);
    		}
    		
    		for (int i = 2;i <= n;i++)
    		{ 
    			ll p;
    			if (i % 2 == 0)
    			{ 
    				p = sum[i] + ji[i] * (n - i / 2) + o[i] * (n - i / 2);
    			}
    			else
    			{ 
    				p = sum[i] + ji[i] * (n - i / 2 - 1) + o[i] * (n - i / 2);
    			}
    			ans = min(ans, p);
    		}
    		cout << ans << endl;
    	}
    }

[Link 1]: https://codeforc.es/contest/1499/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，320人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 64. Minimum Path Sum (动归)

目描述： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV...

曾经终败给现在/ 2024年04月17日 23:28/ 0 赞/ 47 阅读

相关 Minimum Path Sum（C++最小路径和）

（1）动态规划 class Solution { public: int minPathSum(vector<vector<int>>&

快来打我*/ 2022年10月11日 06:17/ 0 赞/ 156 阅读

相关 Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

- 日理万妓/ 2022年09月26日 03:11/ 0 赞/ 110 阅读

相关 LeetCode64——Minimum Path Sum

LeetCode64——Minimum Path Sum 与[LeetCode63——Unique Path II][LeetCode63_Unique Path II] 类

红太狼/ 2022年08月09日 16:49/ 0 赞/ 142 阅读

相关 LeetCode刷题（C++）——Minimum Path Sum（Medium）

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

分手后的思念是犯贱/ 2022年06月16日 06:29/ 0 赞/ 159 阅读

相关 [Leetcode][python]Minimum Path Sum

题目大意从一个矩阵的左上角出发到右下角，只能向右或向下走，找出哪一条路径上的数字之和最小。注意点：所有数字都是非负的解题思路动态规划，承接[htt

布满荆棘的人生/ 2022年06月07日 07:14/ 0 赞/ 134 阅读

相关 LeetCode: Minimum Falling Path Sum

文章目录 Minimum Falling Path Sum 题目描述问题分析 C++实现 Scala实现

超、凢脫俗/ 2022年04月23日 09:10/ 0 赞/ 163 阅读

相关 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

╰半橙微兮°/ 2022年04月21日 22:08/ 0 赞/ 179 阅读

相关 [Leetcode] Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

超、凢脫俗/ 2021年12月03日 07:19/ 0 赞/ 185 阅读

相关 C. Minimum Grid Path (贪心)

[题目][Link 1] 思路：贪心的想如果要使花费尽量小，那就让第一第二小的线段一个向上一个向右尽可能长，只需枚举即可。但是由于有一个每次需要转弯的限制，所以需要分为奇

矫情吗；*/ 2021年07月17日 00:56/ 0 赞/ 321 阅读