Codeforces 1499C. Minimum Grid Path（前缀和，思维优化）

Codeforces 1499C. Minimum Grid Path（前缀和，思维优化）

题目链接

题意：

给出你一个n*n的二维地图，让你从（0，0）走到（n,n）规定：

让你求最小的代价、

思路：

这就是 单方面一维最优。但是我们保证一维最优，另一维却不一定是最优的。所以说不是正解却能启发我们想到正解。

正解：是二维度最优，我们保证二维都是最小的走的步数最多即可保证最终答案最优。所以需要维护二维中的最小值。那我们每次都都比较，记录一下最小值不就行了，然后维护一次前缀因为前面每一个最小都是需要走一段的。我们再加上两位都最小值还需要走的步数(走到终点)，比较取最小值即可。

下面注释的是我原本的错解，看着理解下，提炼出正解嘻嘻。 晚安好梦各位。

#include using namespace std;const int maxn = 3e5 + 10;typedef long long ll;ll a[maxn], b[maxn],c[maxn];ll n, m, cnt, k1, k2;map mp;ll maxx;string str;int main(){ ll t; cin >> t; while(t--) { cin >> n; b[0]=0; for (int i = 1; i <= n; ++i) { cin >> a[i]; b[i] = b[i - 1] + a[i]; } ll ji=a[1],ou=a[2]; maxx =n*a[1]+n*ou; ll ans=2*n; for(int i=3;i<=n;i++){ if(i%2)ji=min(ji,a[i]); else ou=min(ou,a[i]); ll p,q; ll sum=ans-i; p=(sum+1)/2; q=sum/2; maxx=min(maxx,b[i]+q*ji+p*ou); } /*ll ans = 2 * n; for(int i = 2; i <= n; i++) { ll sum = ans - i + 2; ll p, q; p = sum / 2; q = (sum + 1) / 2; maxx = min(maxx, b[i - 2] + q * a[i - 1] + p * a[i]); }*/ cout << maxx << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。