引入

題目描述

經典應用：八皇后問題

dg和udg數組的解釋

對角線 $dg[u+i]dg[u+i]$，反對角線$udg[n?u+i]udg[n?u+i]$中的下標 $u+i$和 $n?u+i$ 表示的是截距
下面分析中的 $(x,y)$ 相當于上面的 $(u,i)$
反對角線 $y=x+b$, 截距 $b=y?x$，因為我們要把 $b$ 當做數組下標來用，顯然 $b$ 不能是負的，所以我們加上 $+n$ （實際上 $+n+4$ , $+2n$都 行），來保證是結果是正的，即 $y?x+n$
而對角線 $y=?x+b$, 截距是 $b=y+x$，這里截距一定是非負的，所以不需要加偏移量
**核心目的：**找一些合法的下標來表示dgdg或udg是否被標記過，所以如果你愿意，你取 $udg[n+n?u+i]$ 也可以，只要所有 $(u,i)$ 對可以映射過去就行

代碼

#include <iostream>using namespace std;const int N = 20;int n;
char g[N][N];
bool col[N], dg[N], udg[N];void dfs(int u)
{if (u == n){for (int i = 0; i < n; i ++ ) puts(g[i]);puts("");return;}for (int i = 0; i < n; i ++ )if (!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q';col[i] = dg[u + i] = udg[n - u + i] = true;dfs(u + 1);col[i] = dg[u + i] = udg[n - u + i] = false;g[u][i] = '.';}
}int main()
{cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0);return 0;
}

例題

題目表述

Codeforce

代碼

#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef long long LL;
typedef pair<int, int> PII;const int N = 410;int T, n, m;
int a[N][N];
int l[N], r[N];int main()
{cin >> T;while(T -- ){memset(l, 0, sizeof l);memset(r, 0, sizeof r);cin >> n >> m;for(int i = 0; i < n; i ++ )for(int j = 0; j < m; j ++ ){cin >> a[i][j];l[i + j] += a[i][j];r[j - i + n] += a[i][j];}int res = -1;for(int i = 0; i < n; i ++ )for(int j = 0; j < m; j ++ ){//注意枚舉到的枚舉加了兩次,還需要減去一次 res = max(res, l[i + j] + r[j - i + n] - a[i][j]);}cout << res << endl;}   return 0;
}