AcWing 80 场周赛 4727.摆放棋子 算法：动态规划

1. f ( i , j , k , u ) f(i, j, k, u) f(i,j,k,u) —— 表示选 i i i 个黑子， j j j 个白子，末尾有连续 k k k 个棋子， u = 0 u = 0 u=0 表示末位是黑子， u = 1 u = 1 u=1 表示末位是白子。

   

   创新互联主营新乡网站建设的网络公司,主营网站建设方案,重庆APP软件开发,新乡h5小程序开发搭建,新乡网站营销推广欢迎新乡等地区企业咨询

2. 状态转移方程：若末位只有一个连续棋子需要特判

f ( i , j , k , 0 ) = f ( i − 1 , j , k − 1 , 0 ) f(i, j, k, 0) = f(i - 1, j, k - 1, 0) f(i,j,k,0)=f(i−1,j,k−1,0)

f ( i , j , k , 1 ) = f ( i , j − 1 , k − 1 , 1 ) f(i, j, k, 1) = f(i, j - 1, k - 1, 1) f(i,j,k,1)=f(i,j−1,k−1,1)

f ( i , j , 1 , 0 ) + = f ( i − 1 , j , k , 1 ) f(i, j, 1, 0) += f(i - 1, j, k, 1) f(i,j,1,0)+=f(i−1,j,k,1)

f ( i , j , 1 , 1 ) + = f ( i , j − 1 , k , 0 ) f(i, j, 1, 1) += f(i, j - 1, k, 0) f(i,j,1,1)+=f(i,j−1,k,0)

时间复杂度 O ( n 1 n 2 × ( k 1 + k 2 ) ) O(n_1 n_2 \times (k_1 + k_2)) O(n1​n2​×(k1​+k2​))

#include#include 
#include#define endl '\n'

#define fup(i, a, b) for (int i = a; i<= b; i ++ )
#define fdn(i, a, b) for (int i = a; i >= b; i -- )

using namespace std;

typedef long long LL;

const int N = 110, M = 15, MOD = 1e8;

int n, m, x, y;
int f[N][N][M][2];

void add(int &a, int b)
{a = (a + b) % MOD;
}

int main()
{cin >>n >>m >>x >>y;
    
    f[1][0][1][0] = f[0][1][1][1] = 1;
    fup(i, 0, n) fup(j, 0, m)
    {if (i) 
        {fup(k, 2, x) f[i][j][k][0] = f[i - 1][j][k - 1][0];
            fup(k, 1, y) add(f[i][j][1][0], f[i - 1][j][k][1]);
        }
        if (j)
        {fup(k, 2, y) f[i][j][k][1] = f[i][j - 1][k - 1][1];
            fup(k, 1, x) add(f[i][j][1][1], f[i][j - 1][k][0]);
        }
    }
    
    int res = 0;
    fup(i, 1, x) add(res, f[n][m][i][0]);
    fup(i, 1, y) add(res, f[n][m][i][1]);
    
    cout<< res<< endl;
    
    return 0;
}

---

简洁写法

1. f ( i , j , k ) f(i, j, k) f(i,j,k) 表示摆好前 i i i 个棋子，其中有 j j j 个白棋， k = 0 k = 0 k=0 表示最后一位为黑棋， k = 1 k = 1 k=1 表示最后一位为白棋。

2. 状态转移方程：若最后一位是白棋，则枚举砍掉最后多少位后剩下的序列的最后一位是黑棋，这里枚举砍掉 k k k 位的范围是 1 ⩽ k ⩽ m i n ( j , x ) 1 \leqslant k \leqslant min(j, x) 1⩽k⩽min(j,x)，表示最后砍掉的部分不能超过当前枚举的连续段的上限以及题目所给的连续长度的上限，下面同理；若最后一位是黑棋，则枚举砍掉最后多少位后剩下的序列的最后一位是白棋，这里枚举砍掉 k k k 位的范围是 1 ⩽ k ⩽ m i n ( i − j , y ) 1 \leqslant k \leqslant min(i - j, y) 1⩽k⩽min(i−j,y)。

f ( i , j , 1 ) + = f ( i − k , j − k , 0 ) f(i, j, 1) += f(i - k, j - k, 0) f(i,j,1)+=f(i−k,j−k,0)

f ( i , j , 0 ) + = f ( i − k , j , 1 ) f(i, j, 0) += f(i - k, j, 1) f(i,j,0)+=f(i−k,j,1)

时间复杂度 O ( ( n 1 + n 2 ) × k 2 ) O((n_1 + n_2) \times k_2) O((n1​+n2​)×k2​)

#include#include 
#include#define endl '\n'

#define fup(i, a, b) for (int i = a; i<= b; i ++ )
#define fdn(i, a, b) for (int i = a; i >= b; i -- )

using namespace std;

const int N = 110, M = N<< 1, S = 15, MOD = 1e8;

int n, m, x, y;
int f[M][N][S];

int add(int &a, int b) 
{return a = (a + b) % MOD;
}

int main()
{cin >>n >>m >>x >>y;
    n += m;
    
    f[0][0][0] = f[0][0][1] = 1;
    fup(i, 1, n) fup(j, 0, min(i, m))
    {fup(k, 1, min(j, y)) add(f[i][j][1], f[i - k][j - k][0]);
        fup(k, 1, min(i - j, x)) add(f[i][j][0], f[i - k][j][1]);
    }
    
    cout<< add(f[n][m][0], f[n][m][1])<< endl;
    
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：【基础DP，但注意写法上的细节】-创新互联
网页路径：http://chengdu.cdxwcx.cn/article/cddeih.html