C. Minimum Grid Path (贪心)

矫情吗；* 2021-07-17 00:56 328阅读 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 条评论，328人围观）

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

相关阅读

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

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

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

相关 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 赞/ 131 阅读

相关 LeetCode64——Minimum Path Sum

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

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

相关 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 赞/ 172 阅读

相关 [Leetcode][python]Minimum Path Sum

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

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

相关 [Leetcode]-64 Minimum Path Sum

刚开始思考用递归来解决该问题： class Solution { public: int minSum(vector<vector<int>

忘是亡心i/ 2022年05月25日 03:29/ 0 赞/ 50 阅读

相关 LeetCode: Minimum Falling Path Sum

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

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

相关 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 赞/ 194 阅读

相关 [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 赞/ 210 阅读

相关 C. Minimum Grid Path (贪心)

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

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