题意:初始时在(1,1),目标(n,m)
位于(x,y)时,每一步只有两种情况:
走到(x,y+1),代价为x
走到(x+1,y),代价为y
问从(1,1)到(n,m)能否花费代价恰好为k
只需判断n×m-1是否等于k大胆猜测小心使用不用证明
其实我们发现,从(x,y)走到(x+1,y+1)只有两种走法,且代价相同。
我们的路径一定是从(1,1)到(n,n)的折线,所以,所有的路线都可以用我们的发现,等价到从(1,1)到(1,n),再从(1,n)到(n,n)的代价
代价为1×(m-1)+m×(n-1)=m×n-1
#include<bits/stdc++.h> using namespace std; long long f(long long m,long long n) { return m*n-1; //return (m-1)+m*(n-1); } int main() { long long t; cin>>t; while(t--) { long long x,y,k; cin>>x>>y>>k; //if(f(x,y)==k|| f(y,x)==k)printf("YES\n"); if(f(x,y)==k) printf("YES\n"); else printf("NO\n"); } return 0; }