格子取数(1)(状態dp)

n*nの格子の碁盤をあげて、各格子の中に非負の数があります.任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.Inputは複数のテストインスタンスを含み、各テストインスタンスは1つの整数nとn*nの非負の数(n<=20)Outputを含み、各テストインスタンスに対して、取得可能な最大およびSample Inputを出力する.

3
75 15 21 
75 15 28 
34 70 5 

Sample Output

188

タイトルは大体:
n*nサイズのマトリクスを与え,与えられたマトリクス内の最大和を探し出し,これらの数の間に隣接できないことを要求した.
考え方:
トウモロコシの栽培に似ています.
ただし、各位置には1つの状態が追加されています.これは、すべての条件に合致する状態を前処理する必要があり、各行の状態の和を前処理する必要があります.
主に前処理が面倒だ.
dp【i】【j】は、i行目までのj状態の最大和である.
方程式dp[i][j]=max(dp[i][j],dp[i-1][k]+stt[i][j]);
コード:

#include 
#include 
#include 
using namespace std;
const int ma=22;
const int mm=21000;
int st[mm];
int stt[ma][mm],dp[ma][mm],map[ma][ma];
int cnt;

void find(int n)
{
    int sum=1<