题解：P13821 「Diligent-OI R2 A」蒹葭苍苍

题目描述

有

n

行空地，其中第

i

行的第

1

列到第

a_i

列都是空地。除了给定的空地以外，其他位置都是障碍物。

你需要从第

1

行最左边的格子走到第

n

行最右边的格子。但你走的过程中只能向上、下或右方向，也不能走出网格。但是可以重复走某个格子，重复走的只算一次，求最多走几个格子。

思路

设

minx_i

为

a_i

到

a_n

的最小值，即

minx_i=\min_{i\le j \le n}\{a_i\}

，在第

i

行最多经过

minx_i

个格子，因为无法往左走，所以第

i

行走的列数不能大于

minx_i

。

代码

CPP

#include <iostream>
using namespace std;

int n;
int a[110];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int minx = 100;
	int ans = 0;
	for (int i = n; i; i--) {
		minx = min(minx, a[i]);
		ans += minx;
	}
	cout << ans;
	return 0;
}

题解：P13821 「Diligent-OI R2 A」蒹葭苍苍

文章操作

题目描述

思路

代码

相关推荐

评论

题解：P13821 「Diligent-OI R2 A」蒹葭苍苍