CF1332 D. Walk on Matrix

題意

給你一個 $k(0\le k\le 105)$k(0≤k≤105)
要求你構造一個 $n\times m$n×m的矩陣滿足下列條件

1. $1\le n,m\le 500$1≤n,m≤500
2. $0\le a_{i,j}\le 3?10^5$0≤ai,j?≤3?105
3. 由以上dp式子推出來的 $dp\left[n\right]\left[m\right]$dp[n][m]和真正路徑最大位與相差k

思路

構造
首先這題是位于運算且和dp式子有關，我們可以將題目中的樣例2轉為二進制之后，去手動模擬一下為什么dp答案是錯的?

我們發(fā)現 $d{p}_{3,3}$dp3,3?不一樣導致了結果不一樣，那么 $d{p}_{3,3}$dp3,3?為什么會不一樣呢？
因為 $d{p}_{3,3}$dp3,3?取了 $d{p}_{3,2}$dp3,2?，那么為什么會這么??？
我們思考發(fā)現 $dp$dp的結果會取到大的數，但是這道題不能用dp做的原因在于這道題是有后效性的。我們前面選擇了大的數，最終的結果不一定會是大的數。

說到這里再來復習一下 $dp$dp的條件：

1. 最優(yōu)子結構性質： 由前面子問題的最優(yōu)解可以推的后續(xù)子問題的最優(yōu)解
2. 無后效性：前面的解怎么來的不會影響到后續(xù)的解
3. 子問題的重疊性： 可以把一個大規(guī)模的問題分為若干個小規(guī)模的問題，它們的本質是一樣的。

我們思考一下如何構造相差k，為了簡化問題，我們可以想辦法讓dp式子得出來的結果為0，那么只要再讓路徑最大位與的結果為k即可。
我們這里需要利用dp錯誤的原因在于他會優(yōu)先取大的數，那我們就給他構造一個較大的數。

我們要取到k都能位與得到結果，?全部取1即可。

這樣還是不夠的，因為我們如果在 $a_{2,2}$a2,2?放入k，他會取左邊的。

結合題目條件 $1\le n,m\le 500$1≤n,m≤500 $0\le a_{i,j}\le 3?10^5$0≤ai,j?≤3?105 $k(0\le k\le 105)$k(0≤k≤105)
我們確定數據范圍 $2^{18}\approx 2.6e52^{17}\approx 1.3e52^{19}\approx 5.2e5$218≈2.6e5217≈1.3e5219≈5.2e5
我們發(fā)現若取 $2^{19}$219則超出a數組的范圍，若取 $2^{17}$217則當k為1e5時會出現問題。
所以我們只能取2e18-1來構造。

推廣

這道題如果再加深難度，就是構造一個要求長為n寬為m的一個矩陣，這時候應該再上面構造的基礎上拓展成這樣的形式

#include<bits/stdc++.h>
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;
}