CF1499 C Minimum Grid Path

知识点：枚举最值、前缀和、贪心

题目链接

题意

从$(0,0)$走到$(n,n)$只能选择初始方向和向右或向上交替行走，每步行走任意长度，但路径最多只有$n$段且第$i$步有固定$cost$值$a_i$，设第$i$步长度为$le{n}_i$，求${\sum }_{i=1}^k{a}_i\times le{n}_i$最小值，其中$1\le k\le n$。

思路

因为这是典型的枚举最值问题，所以当做个人题解

不难想到答案与初始方向无关（不妨设向右）且向上和向右的所有行走相互“独立”（直观印象），所以按照第i步奇偶分组。
通过分析待求式子可知相当于在路径上的每一条单位线段上填上$a_i$（该单位线段属于第i步），那么贪心使$a_i$小的段尽量长，其他尽量短，即走到第i步时，其他只走长度为1，最小值走长度为$n-(k-1)$（k为第i步走过的奇/偶位置数量，k-1为除去第i步的奇/偶位置数量），$n-(k-1)$取一个单位分到k-1里可以构成一个n-k长度的最小值和前k个奇/偶位置的前缀和。
第一次尝试直接维护所有奇/偶位置上的最小值，走到后一个最值结束，wa3。对拍后发现该方法只是走到后一个最小值所在步数时的贡献，实际上所有走到第i步都有贡献，要维护第i步奇/偶位置上的最小值。变成典型的枚举最值。

代码

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const ll N=1e5+10;

ll n;
ll arr[N];

void solve()
{
   
	scanf("%lld",&n);
	for(ll i=1; i<=n; i++) scanf("%lld",&arr[i]);
	ll mnodd=1,mneven=2;//第i步奇/偶位置最小值下标
	ll cntodd=1,cnteven=1;//第i步奇/偶位数量
	ll ans=n*(arr[1]+arr[2]);
	ll sum=arr[1]+arr[2];//第i步前缀和（奇偶一起维护）
	for(ll i=3;i<=n;i++)
	{
   
		sum+=arr[i];
		if(i&1)
		{
   
			cntodd++;
			if(arr[i]<arr[mnodd]) mnodd=i;//更新第i步最小值位置
			ans=min(ans,sum+(n-cntodd)*arr[mnodd]+(n-cnteven)*arr[mneven]);
			//(n-cntodd)*arr[mnodd]：奇数位置上长度为n-cntodd的最小值，偶数位置同理
		}else
		{
   
			cnteven++;
			if(arr[i]<arr[mneven]) mneven=i;
			ans=min(ans,sum+(n-cntodd)*arr[mnodd]+(n-cnteven)*arr[mneven]);
		}
	}
	printf("%lld\n",ans);
}

int main()
{
   
	ll t;
	scanf("%lld",&t);
	while(t--)
		solve();
	return 0;
}