1499C Minimum Grid Path

题面:

假设你在 \(X*Y\) 的平面中，开始点为 \((0,0)\) ，要达到 \((n,n)\)

你只有两种移动方式：

• 向右移动，即 \(x\) 坐标增加
• 向上移动，即 \(y\) 坐标增加

你不太喜欢改变方向，因此你改变不多于 \(n-1\) 次方向。

最终，你的路径会形成一个多边形，最多有 \(n\) 条线段。所有路径的造价并不相同，你有 \(n\) 个整数 \(c_1,c_2, \dots ,c_n\) ，每个 \(c_i\) 都代表了第 \(i\) 个的花费。

我们所花费的总代价就是 \(\sum_{i=1}^{k} c_i · length_i\)

求不超过 \(n\) 段时的最低费用

思路：

根据画图+贪心我们可以知道以下两点：

• 奇数位 \(i\) 时向上，偶数位 \(i\) 时向右
• 如果想要某一方向上最少，则只要找到这个方向上当前花费最少的，花费最少的走的最多，其他的都只走一次

根据上面的两点，可以总结出对某一个位置 \(i\) 的花费计算公式：

注： \(min_y\) 为当前位置上，所有 \(c_y\) 的最小值； \(cnt_y\) 为当前位置上，所有 \(c_y\) 的个数， \(sum\) 为前面所有 \(c\) 的总和

标签：

贪心 数学 暴力 CF 1500

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1e16;

int main()
{
	int T;
	cin >> T;
	while(T--){
		ll n;
		cin >> n;
		ll res = INF, sum = 0, cnt_x = 0, cnt_y = 0,min_x = 1e9, min_y = 1e9;
	
		for(int i = 1 ; i <= n ; i++){
			ll temp;
			cin >> temp;
			if(i&1){
				min_x = min(min_x,temp), cnt_x++;
			}else{
				min_y = min(min_y,temp), cnt_y++;
			}
		
			sum += temp;
			res = min(res,sum + min_x * (n-cnt_x) + min_y * (n-cnt_y));
		}
		cout << res << endl;
	}
}

Codeforces 1499C Minimum Grid Path

原文：https://www.cnblogs.com/ieeeev/p/14585512.html