原题链接
题意：
从( 0 , 0 ) (0,0)(0,0)走到( n , n ) (n,n)(n,n)，每次只能向上或向右走，并且方向一定要改变。第i ii段路的花费为l e n ∗ c i len*c_{i}len∗c
i
，求最小的花费。
拐弯次数最多为n − 1 n-1n−1
思路：
由于每走一次后方向都要改变一次，所以就想到了分奇偶讨论，然后思路就卡住了。
贪心没想出来，只想出来了个O ( n 3 ) 的 d p O(n^{3})的dpO(n
3
)的dp。
下面的思路是KingZhang的，wtcl。
首先，c cc数组是不能排序的，因为计算花费的时候是有顺序的。
其次，由于每次都要改变方向，所以可以将x轴的花费和y轴的花费分开考虑，其实走的距离都是一样的，具体对应关系没有限制。
然后，考虑如何使得花费最小。以x轴的花费为例：由于拐弯次数可以小于n-1，我们可以选择一个最小的数走完全程，这样会使得花费减少。但是要注意最小的数前面的数是必须要选的，这就可以通过枚举来解决，而不是单一的确定值。假设现在已经走了k的距离，那么剩下的就是n-k的距离都是由最小的数完成，这样花费是最小的。前者可以用前缀和解决。
y轴的情况也同理。
注意上面的情况只是方便计算，实际走的时候是最小的数走了n-k+1的距离才更换的方向。
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read() { ll x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-')f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b, ll p) { ll res = 1; while(b) { if(b & 1)res = res * a % p; a = a * a % p; b >>= 1; } return res; } const int inf = 0x3f3f3f3f; #define PI acos(-1) const double eps = 1e-8; const int maxn =1e6+7; ll n,c[maxn],a[maxn]; void solve(){ n=read; a[0]=0; rep(i,1,n){ c[i]=read;//花费数组 a[i]=a[i-1]+c[i];//维护前缀和 } ll tmpj=c[1],tmpo=c[2]; ll res=n*(tmpj+tmpo);//假设不拐弯走完全程 rep(i,3,n){ if(i%2==1) tmpj=min(tmpj,c[i]);//分别维护最小值 else tmpo=min(tmpo,c[i]); ll t=2*n-i;//总共还需要走的长度 ll t2=t/2,t1=t-t2;//分给x轴和y轴 res=min(res,a[i]+t2*tmpj+tmpo*t1);//a[i]表示之前的路的花费，后面两个表示到终点的花费 } cout<<res<<endl; } int main() { int T=read; while(T--) solve(); return 0; }
