ACM必备模板——动态规划

2023-11-15 10:38:16

动态规划

文章目录

背包问题

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;
}
红与黑
  • BFS
#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;
}
  • dfs

#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;
}
上一篇：实验3 转移指令跳转原理及其简单应用编程


下一篇：ACM 任务