CF1332 D. Walk on Matrix

题意

给你一个$k(0\le k\le 105)$
要求你构造一个$n\times m$的矩阵满足下列条件

1. $1\le n,m\le 500$
2. 0 ≤ a i , j ≤ 3 ⋅ 1 0 5 0≤a_{i,j}≤3⋅10^5 0≤ai,j​≤3⋅105
3. 由以上dp式子推出来的$dp[n][m]$和真正路径最大位与相差k

思路

构造
首先这题是位于运算且和dp式子有关，我们可以将题目中的样例2转为二进制之后，去手动模拟一下为什么dp答案是错的?

我们发现 d p 3 , 3 dp_{3,3} dp3,3​不一样导致了结果不一样，那么 d p 3 , 3 dp_{3,3} dp3,3​为什么会不一样呢？
因为 d p 3 , 3 dp_{3,3} dp3,3​取了 d p 3 , 2 dp_{3,2} dp3,2​，那么为什么会这么取？
我们思考发现$dp$的结果会取到大的数，但是这道题不能用dp做的原因在于这道题是有后效性的。我们前面选择了大的数，最终的结果不一定会是大的数。

说到这里再来复习一下$dp$的条件：

1. 最优子结构性质： 由前面子问题的最优解可以推的后续子问题的最优解
2. 无后效性：前面的解怎么来的不会影响到后续的解
3. 子问题的重叠性： 可以把一个大规模的问题分为若干个小规模的问题，它们的本质是一样的。

我们思考一下如何构造相差k，为了简化问题，我们可以想办法让dp式子得出来的结果为0，那么只要再让路径最大位与的结果为k即可。
我们这里需要利用dp错误的原因在于他会优先取大的数，那我们就给他构造一个较大的数。

我们要取到k都能位与得到结果，?全部取1即可。

这样还是不够的，因为我们如果在 a 2 , 2 a_{2,2} a2,2​放入k，他会取左边的。

结合题目条件$1\le n,m\le 500$ 0 ≤ a i , j ≤ 3 ⋅ 1 0 5 \quad0≤a_{i,j}≤3⋅10^5 0≤ai,j​≤3⋅105 $k(0\le k\le 105)$
我们确定数据范围 2 18 ≈ 2.6 e 5 2 17 ≈ 1.3 e 5 2 19 ≈ 5.2 e 5 2^{18}\approx2.6e5 \quad 2^{17}\approx1.3e5\quad 2^{19}\approx5.2e5 218≈2.6e5217≈1.3e5219≈5.2e5
我们发现若取 2 19 2^{19} 219则超出a数组的范围，若取 2 17 2^{17} 217则当k为1e5时会出现问题。
所以我们只能取2e18-1来构造。

推广

这道题如果再加深难度，就是构造一个要求长为n宽为m的一个矩阵，这时候应该再上面构造的基础上拓展成这样的形式

#include
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;int main(){ios::sync_with_stdio(false);cin.tie(0);int k;cin>>k;cout<<2<<" "<<3<<'\n';cout<<(1<<18)-1<<" "<<(1<<17)<<" "<<0<<'\n';cout<<k<<" "<<(1<<17)+k<<" "<<k<<'\n';return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！