CF1700A Optimal Path 题解

题意简述

给定 $t$ 组数据，每组数据有两个整数 $n,m$，表示有一个 $n \times m$ 的矩阵。

矩阵的每个点都有值，表示到这个点要的成本，且这个值为 $a_{ij} = (i-1) \cdot m + j$。

现在要从 $(1,1)$ 到 $(n,m)$，问最小成本。

解题思路

这里的最优解就是先横着走，再竖向走。

因为在第一行横着走时，$i-1 = 0$，此时 $a_{ij} = j$。而向下走成本都是一样的，可以证明这种走法最优。

横向走的成本(等差数列优化到 $\Theta (1) $ 级别)：

$ans_1 = \dfrac{(m+1) \cdot m}{2}$

竖向走的成本：

$ans_2 = \dfrac{(m + m * n)* n}{2}$

总成本（有个 $m$ 重复算了，要减掉）：

$ans = ans_1 + ans_2 - m$

最后，一定要开 long long。

代码实现

#include<bits/stdc++.h>
using namespace std;
long long t,n,m;
int main() {
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d",&n,&m);
		long long ans1=m*(m+1)/2;
		long long ans2=n*(m+m*n)/2;
		printf("%lld\n",ans1+ans2-m);
	}
	return 0;
}
//code by TheCedar