题意:给定一个二维数组,只能从i,j走到i+1,j或i,j+1,且必须保证值从x走到x+1,给你一种变换,aij=aij-1,要求出到达n,m点的最小操作数。
思路:贪心的来想对于一条合法的最小路径来说,它不可能所有经过的点都进行过-1操作,因为如果都进行过-1,考虑相对大小关系,相当于都没-1,因此,总有至少一个数是保持不变的,枚举这个数,固定其他值(axy+(i-x)+(j-y))dp最小操作就行
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- //#include
-
- //#define int ll
- #define IOS std::ios::sync_with_stdio(false);std::cin.tie(0);
- #define pb push_back
- #define endl '\n'
- #define x first
- #define y second
- #define Endl endl
- #define pre(i,a,b) for