前言
老少皆宜。
题目
题目大意:
(t) 组数据,每组数据有三个整数 (n,m,k),询问是否存在一条路径从 ((1,1)) 到 ((n,m)) 的花费恰好为 (k)。
你有两种行走方式:
- 从 ((x,y)) 走到 ((x,y+1)),花费为 (x)。
- 从 ((x,y)) 走到 ((x+1,y)),花费为 (y)。
(1le t le 100 ; 1le n,mle 100 ; 0le k le 10^4.)
讲解
我们可以通过瞪眼或者打表发现,无论你选择任何一条路径,花费恒为 (nm-1) 。
考虑归纳证明。
特殊地:
当我们位于 ((1,1)) 时,花费为 (0),成立。
一般地:
当我们从 ((n-1,m)) 走向 ((n,m)) 时,花费为 ((n-1)*m-1+m=n*m-1),成立。
当我们从 ((n,m-1)) 走向 ((n,m)) 时,花费为 (n*(m-1)-1+n=n*m-1),成立。
也就是说我们可以通过递推证明。
然后你就可以写出一份优秀的 (O(T)) 的代码。
代码
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T = Read(); T ;-- T)
{
n = Read(); m = Read(); k = Read();
if(k == (n*m)-1) printf("YES
");
else printf("NO
");
}
return 0;
}