开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> ACM必备模板——动态规划 -> 正文阅读

[数据结构与算法]ACM必备模板——动态规划

动态规划

文章目录

动态规划

背包问题

01背包 ——每件物品只能使用一次。

状态方程：f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);

二维

#include<iostream>
#include<algorithm>


using namespace std;

const int N =10010;

int v[N],w[N];  // 体积  ，价值
int f[N][N];    // f[i][j] : 表示前 i 个 总体积不超过j
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
    //f[0][0~m] =0 
    
    for(int i=1;i<=n;i++) 
        for(int j=0;j<=m;j++)
        {
            f[i][j]= f[i-1][j];
            if(j>=v[i]) f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
        }
    cout<<f[n][m]<<endl;
     
    
    
    return 0;
}

一维

#include<iostream>
#include<algorithm>

using namespace std;

const int N =1010;

int n,m;
int v[N],w[N];
int f[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)
            f[j]= max(f[j],f[j-v[i]]+w[i]);
        
    cout<<f[m];
    return 0;
}

完全背包 —— 每种物品都有无限件可用。

二维

状态方程：

完全背包： f[i][j]= max(f[i][j],f[i][j-v[i]]+w[i]);
0 1背包：f[i][j]= max(f[i][j],f[i-1][j-v[i]]+w[i]);

#include<iostream>
#include<algorithm>

using namespace std;

const int N =1010;

int  n,m;
int v[N],w[N];
int f[N][N];

int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          {
              f[i][j]=f[i-1][j];
              if(j>=v[i])
              f[i][j]= max(f[i][j],f[i][j-v[i]]+w[i]);
          }
    cout<<f[n][m]<<endl;      
    return 0;
}

一维

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1010;

int n,m;
int v[N],w[N];
int f[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)
              f[j]=max(f[j],f[j-v[i]]+w[i]);
          
    cout<<f[m];
    return  0;
}

多重背包——第 i 种物品最多有 si 件

暴力写法

状态表示：
f[i][j]: 在前i个数中选,总体积不超过j；

状态计算：
f[i][j] = max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k); (k:0~该数最多取几个)

#include<iostream>
#include<algorithm>

using namespace std;
const int N =110;

int n,m;
int v[N],w[N],s[N];
int f[N][N];

int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j] = max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
    
    cout<<f[n][m]<<endl;            
    return 0;
}

二进制优化写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) // k取 1,2,4,8.……,  <=s
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)   // s还有就直接放进去
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;
    
    //01背包
    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

分组背包——每组物品有若干个，同一组内的物品最多只能选一个。


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for (int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];   // 体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
    }

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k < s[i]; k ++ )
                if (v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

    cout << f[m] << endl;


    return 0;
}

背包问题中的方案数问题

原始做法

#include <iostream>

using namespace std;

const int N = 10010, M = 110;
int f[N][N], a[M];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] = 1;
        for (int j = 1; j <= m; j++) {
            f[i][j] = f[i - 1][j];
            if (j >= a[i]) f[i][j] += f[i - 1][j - a[i]];
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

优化空间

#include <iostream>

using namespace std;

const int N = 10010, M = 110;
int f[N], a[M];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= a[i]; j--) f[j] += f[j - a[i]];
    }
    cout << f[m] << endl;

    return 0;
}

线性DP

数字三角形

#include<bits/stdc++.h>

using namespace std;

const int N = 510;
int n;
int w[N][N];  // 原三角形数。
int f[N][N];  //f[i][j]: 自下向上 到达 f[i][j]的路径最大值
int main()
{ 
    cin>>n;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>w[i][j];  

    for(int j=1;j<=n;j++)
        f[n][j] = w[n][j];  // 对三角形最底层的数 初始化

    for(int i=n-1;i;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);   //自下向上推

    cout<<f[1][1]<<endl;


    return 0;
}

最长上升子序列

朴素写法

状态方程：if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=1010;
int f[N];
int a[N];
int n; 
int main(){
	 cin>>n;
	 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	 
	 for(int i=1;i<=n;i++){
	 	f[i]=1;   // 初始只有a[i] 
		
		for(int j=1;j<i;j++)
		 	if(a[j]<a[i]) 
				f[i]=max(f[i],f[j]+1);
		 
	 }
	 
	 int res=1;
	 for(int i=1;i<=n;i++)res=max(res,f[i]);
	 
	 cout<<res;	
	 
	
	return 0;
}

二分写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }

    printf("%d\n", len);

    return 0;
}

最长公共子序列

集合表示：f[i][j]表示a的前i个字母，和b的前j个字母的最长公共子序列长度
集合划分：以a[i],b[j]是否包含在子序列当中为依据，因此可以分成四类：

#include <iostream>

using namespace std;

const int N = 1010;

int n , m;
char a[N] , b[N];
int f[N][N];
int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            {
                f[i][j] = max(f[i - 1][j] , f[i][j - 1]);//②和③的情况一定存在，所以可以无条件优先判断
                if(a[i] == b[j]) f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);
            }                                                       

    cout << f[n][m] << endl;
    return 0;
}

区间DP

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 310;

int f[N][N]; // f[i][j]: 在（i，j）区间的最小代价
int s[N];
int n;

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )cin>>s[i],s[i]+=s[i-1];
    
    for (int len = 2; len <= n; len ++ ){
        for (int i = 1; i+len-1 <= n; i ++ ){
            int l = i;
            int r = l+len-1;
            f[l][r]=1e8;
            for (int k = l; k <=r; k ++ ){
                f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    }
    cout<<f[1][n];
    return 0;
}

记忆化搜索

例题：滑雪场

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

int n, m;
int g[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int &v = f[x][y];
    if (v != -1) return v;

    v = 1;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
            v = max(v, dp(a, b) + 1);
    }

    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &g[i][j]);

    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res = max(res, dp(i, j));

    printf("%d\n", res);

    return 0;
}

杂论补充

贪心

区间问题

区间选点

给定 N 个闭区间 [ai,bi] ，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 100010;

struct Range{    // 区间的结构体
  int l,r;
  bool operator<(const Range &w)const{   // 重载小于运算符： 为了sort用

      return r<w.r;
  }

}range[N];

int n,a,b;
int main()
{   
    cin>>n;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d", &a, &b);
        range[i]={a,b};
    } 

    sort(range,range+n); // 按右端点排序（小到大）

    int res=0,ed=-2e9;   // ed : 区间端点，因为刚开始还没有设置 。所以设置非常小的数
    for (int i = 0; i < n; i ++ )
    {
        if(range[i].l>ed)   // 如果当前区间的左端点在选出点的右边，说明当前区间和之前区间不重合， 需要个数++。 然后把选出点，设置为当前区间的右端点。
        {
            res++;
            ed=range[i].r;
        }
    }

    cout << res;
    return 0;

最大不相交的区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Range{
  int l,r;
  bool operator<(const Range &w)const{
      return r<w.r;
  }
}range[N];

int n;
int a,b;
int main()
{
    cin>>n;
    for (int i = 0; i < n; i ++ ){
        cin>>a>>b;
        range[i]={a,b};
    }

    sort(range,range+n);

    int res =0,ed=-2e9;
    for (int i = 0; i < n; i ++ ){
        if(range[i].l>ed){
            res++;
            ed=range[i].r;
        }

    }
    cout<<res;
    return 0;
}

区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++ )
    {
        auto r = range[i];
        if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
        else
        {
            heap.pop();
            heap.push(r.r);
        }
        
    }

    printf("%d\n", heap.size());

    return 0;
}

区间覆盖

给定 N 个闭区间 [a**i,b**i] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 ?1。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++ ;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res ++ ;
        if (r >= ed)
        {
            success = true;
            break;
        }

        st = r;
        i = j - 1;
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}

哈夫曼树——合并果子

合并任意两堆

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int n,x;
priority_queue<int, vector<int>,greater<int>>heap;

int main()
{
    cin >> n;
    while (n -- )cin>>x,heap.push(x);
    int res=0;    
    while(heap.size()>1){
        int a = heap.top();heap.pop();
        int b = heap.top();heap.pop();
        res+=(a+b);
        heap.push(a+b);
    }
    cout << res;
    return 0;
}

绝对值不等式——货场选址

在一条数轴上有 N 家商店，它们的坐标分别为 A1～AN。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

结论： if（n == 奇数）选中位数 else 选中间两数中间（记得排序）

注：中位数不管是奇数还是偶数，都可以写做a[n/2]

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int a[100010];
int main(){
    cin >> n;
    for (int i = 0; i < n; i ++ )scanf("%d",&a[i]);
    
    sort(a,a+n);
    
    int res=0;
    for (int i = 0; i < n; i ++ ) res+=abs(a[i]-a[n/2]);
    cout << res;
    return 0;
}

数论

约数个数

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 1e9+7 取模。

/*
    如果 N = p1^c1 * p2^c2 * ... *pk^ck
    约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
    约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

*/
#include<iostream>
#include<unordered_map>
using namespace std;

typedef long long LL;

const int N=110,mod=1e9+7;

int main(){
    int n;
    cin>>n;

    unordered_map<int,int>primes;

    while(n--){
        int x;
        cin>>x;

        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }   
    LL res=1;
    for(auto p:primes)res=res*(p.second+1)%mod;

    cout<<res<<endl;

    return 0;
}

约数之和

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 1e9+7 取模。


/*
    如果 N = p1^c1 * p2^c2 * ... *pk^ck
    约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
    约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)

*/
#include<iostream>
#include<unordered_map>
using namespace std;

typedef long long LL;

const int N=110,mod=1e9+7;

int main(){
    int n;
    cin>>n;

    unordered_map<int,int>primes;

    while(n--){
        int x;
        cin>>x;

        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1)primes[x]++;
    }   
    /* 约数个数 
    LL res=1;
    for(auto p:primes)res=res*(p.second+1)%mod;

    cout<<res<<endl;
    */

    /*约数之和 */ 


    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout << res << endl;
    return 0;
}

搜索进阶

Flood Fill

连通块的个数

池塘计数

#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || st[i][j]) continue;

                q[ ++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);

    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++ ;
            }

    printf("%d\n", cnt);

    return 0;
}

红与黑

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second

int m,n;
char g[25][25];

int bfs(int sx,int sy)
{
	queue<PII>q;
	q.push({sx,sy}); // @ 坐标  入队。
	g[sx][sy]='#'; // 入队后 ，标记已走过。
	int res=0;
	           //偏移量 ： {上，右，下，左} 
	int dx[]={-1,0,1, 0}; //行方向 
	int dy[]={ 0,1,0,-1}; //列方向
	
	while(q.size()) 
	{
		PII t= q.front();
		q.pop();
		res++;
		
		for(int i=0;i<4;i++) //遍历 四个方向的邻点 
		{
			int x=t.x+dx[i],y=t.y+dy[i];
			if(x<0||x>=n||y<0||y>=m||g[x][y]!='.')continue;
			g[x][y]='#';
			q.push({x,y});
		 } 
	}
		
	return res;
}
int main()
{ 
	while(cin>>m>>n,n||m)  // m  列  n  行 
	{
		for(int i=0;i<n;i++) cin>>g[i]; //输入n行字符串
		int x,y;// @ 所在位置的坐标
		
		for(int i=0;i<n;i++)         // 寻找 @的所在位置 
			for(int j=0;j<m;j++)
	 			if(g[i][j]=='@')
	 			{
				   x=i;y=j;
				} 
				
		cout<<bfs(x,y)<<endl;		
		 
	}
       
  return 0;
}


#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25;

int n, m;
char g[N][N];
bool st[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x, int y)
{
    int cnt = 1;

    st[x][y] = true;
    for (int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (g[a][b] != '.') continue;
        if (st[a][b]) continue;

        cnt += dfs(a, b);
    }

    return cnt;
}

int main()
{
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++ ) cin >> g[i];

        int x, y;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == '@')
                {
                    x = i;
                    y = j;
                }

        memset(st, 0, sizeof st);
        cout << dfs(x, y) << endl;
    }

    return 0;
}

DFS

排列数字

#include<bits/stdc++.h>
using namespace std;

const int N=10;
int a[N];
bool st[N];  // 记录 哪些数是用过的
int n;

void dfs(int x)
{
    if(x==n)
    {
        for(int i=0;i<n;i++) printf("%d ",a[i]);        
        puts("");
        return;
    }
                                      // 之所以 i 从 0， 是因为 x 是从 0 开始的
    for(int i=0;i<n;i++) 
    {
        if(!st[i])
        {
            st[i]=true; // 标记

            a[x]=i+1;
            dfs(x+1);

            st[i]=false; // 恢复现场。 
        }
    }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
 }

n-皇后问题

#include<bits/stdc++.h>
using namespace std;

const int N=10;
int col[N],ug[2*N],dug[2*N];
bool st[N];
char a[N][N];
int n;

void Dfs(int x)
{
    if(x==n)
    {
        for(int i=0;i<n;i++)
        {
           puts(a[i]);
        //    puts("");
        }
        puts("");
        return;
    }
    for(int i=0;i<n;i++)
    {                                      
                                           /*
                                          dug[y-x+n]： y = x + b ----> b = y - x (由于y-x 可能是负)--->  b = y - x +n
                                          ug[i+x]  :  y = -x+b ------> b = y + x


                                           */
        if(!col[i]&&!ug[i+x]&&!dug[i-x+n])
         {
            col[i]=ug[i+x]=dug[i-x+n]=1;
            a[x][i]='Q';
            Dfs(x+1);
             col[i]=ug[i+x]=dug[i-x+n]=0;
             a[x][i]='.';
         }

    }

}
int main()
{

    cin>>n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            a[i][j] = '.';
    Dfs(0);
    return 0;
}

记

        a[x]=i+1;
        dfs(x+1);

        st[i]=false; // 恢复现场。 
    }
}

}

int main()
{
cin>>n;
dfs(0);
return 0;
}


###### n-皇后问题

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=10;
int col[N],ug[2*N],dug[2*N];
bool st[N];
char a[N][N];
int n;

void Dfs(int x)
{
    if(x==n)
    {
        for(int i=0;i<n;i++)
        {
           puts(a[i]);
        //    puts("");
        }
        puts("");
        return;
    }
    for(int i=0;i<n;i++)
    {                                      
                                           /*
                                          dug[y-x+n]： y = x + b ----> b = y - x (由于y-x 可能是负)--->  b = y - x +n
                                          ug[i+x]  :  y = -x+b ------> b = y + x


                                           */
        if(!col[i]&&!ug[i+x]&&!dug[i-x+n])
         {
            col[i]=ug[i+x]=dug[i-x+n]=1;
            a[x][i]='Q';
            Dfs(x+1);
             col[i]=ug[i+x]=dug[i-x+n]=0;
             a[x][i]='.';
         }

    }

}
int main()
{

    cin>>n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            a[i][j] = '.';
    Dfs(0);
    return 0;
}