活动 - AcWinghttps://www.acwing.com/activity/content/punch_the_clock/11/

目录

一、背包问题

1.01背包

2.完全背包

3.多重背包

3.分组背包

二、线性DP

1.数字三角形

2.最长上升子序列

3.最长公共子序列

4.编辑距离

三、区间DP

石子合并

四、计数类DP

整数划分

五、数位统计DP

计数问题

六、状态压缩DP

1.蒙德里安的梦想

2.最短Hamilton路径

七、树形DP

没有上司的舞会

八、记忆化搜索

滑雪

---

一、背包问题

以下代码块中数据输入均可直接进行状态转移操作，节省空间。

1.01背包

#include 
using namespace std;

const int N = 1e3 + 10;
int v[N], w[N];    // 花费、价值

void solve1(){
    int dp[N][N];    // 前i个物品中容量为j时的最大价值
    int n, m;
    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 = 0; j <= m; j ++){    // 枚举容积
            if(j < v[i]) dp[i][j] = dp[i - 1][j];    // j的容积装不下第i件物品
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);    // max(不装, 装)
        }
    }
    cout << dp[n][m];    // 答案状态
}

// 降维 滚动数组优化：dp[i][]都由dp[i-1][]转移而来 
void solve2(){
    int dp[100000];    // 容量为j时的最大价值
    int n, m;
    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 --){    // 逆序枚举 防止污染前面状态
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve2();
}

2.完全背包

#include 
using namespace std;

const int N = 1e3 + 10;
int v[N], w[N];    // 花费、价值

// 基本思路（会T）
void solve1(){
    int dp[N][N];    // 前i个物品中容量为j时的最大价值
    int n, m;
    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 = 0; j <= m; j ++)    // 枚举容积
            for(int k = 0; k * v[i] <= j; k ++){ // 枚举能装几件i物品
                dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            }
    
    cout << dp[n][m];    // 答案状态
}

// 优化
void solve2(){
    int dp[N][N];    // 前i个物品中容量为j时的最大价值
    int n, m;
    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 = 0; j <= m; j ++){    // 枚举容积
            if(j < v[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);    // 区别01背包的地方：可拿多次i物品
        }
    
    cout << dp[n][m];    // 答案状态
}

// 降维优化
void solve3(){
    int dp[100000];    // 容量为j时的最大价值
    int n, m;
    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 ++){    // 区别01背包为逆序枚举
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[m];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve1();
}

3.多重背包

#include 
using namespace std;

const int N = 1e5 + 10;
int v[N], w[N], c[N];    // 花费、价值、数量
int dp[1010][1010];    // 前i个物品中容量为j时的最大价值
int dp[N];    // 容量为j时的最大价值

// 多包问题基本思路 类比完全背包
void solve1(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> c[i];
    
    for(int i = 1; i <= n; i ++)    // 枚举物品编号
        for(int j = 0; j <= m; j ++)    // 枚举容积
            for(int k = 0; k <= c[i]; k ++){ // 枚举能装几件i物品
                if(j >= k * v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
            }
    
    cout << dp[n][m];    // 答案状态
}

// 优化（数据太水）
void solve2(){
    int n, m;
    cin >> n >> m;
    
    // 将一定数量的每种物品分成一个个物品
    int id = 1;
    for(int vol, weal, num, i = 1; i <= n; i ++){
        cin >> vol >> weal >> num;
        while(num --){
            v[id] = vol;
            w[id] = weal;
            id ++;
        }
    }
    
    // 转化为01背包问题
    for(int i = 1; i < id; i ++)    // 枚举物品组号
        for(int j = m; j >= v[i]; j --){    // 枚举容积
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    
    cout << dp[m];    // 答案状态
}

// 二进制优化
void solve3(){
    int n, m;
    cin >> n >> m;
    
    // 分组
    int id = 1;
    for(int vol, weal, num, i = 1; i <= n; i ++){
        cin >> vol >> weal >> num;
        int k = 1;
        while(k <= num){
            v[id] = k * vol;
            w[id ++] = k * weal;
            num -= k;
            k <<= 1;
        }
        // 剩余一组
        if(num > 0){
            v[id] = num * vol;
            w[id ++] = num * weal;
        }
    }
    
    // 转化为01背包问题
    for(int i = 1; i < id; i ++)    // 枚举物品组号
        for(int j = m; j >= v[i]; j --){    // 枚举容积
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    
    cout << dp[m];    // 答案状态
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve3();
}

3.分组背包

#include 
using namespace std;

const int N = 1e5 + 10;
int v[N], w[N];    // 花费、价值
int dp[N];

// 分组背包 => 多重01背包
void solve(){
    int n, m;
    cin >> n >> m;
    while(n --){
        int t;
        cin >> t;
        for(int i = 1; i <= t; i ++) cin >> v[i] >> w[i];
        
        // 01背包 每组最多拿一个
        for(int j = m; j >= 0; j --)    
            for(int i = 1; i <= t; i ++){    // 遍历每组的每个物品
                if(j >= v[i]) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
    }
    cout << dp[m];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

二、线性DP

1.数字三角形

#include 
using namespace std;

#define int long long
const int N = 5e2 + 10;
int dp[N][N];    // 走到(i, j)的最大和
int g[N][N];

void solve(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= i; j ++) cin >> g[i][j];
    }

    // 倒着走 无需考虑边界问题 因为最优路径的和不变
    for(int i = n; i >= 1; i --)
        for(int j = i; j >= 1; j --){
            // (i,j)状态由矩阵正下(i+1, j)或右下(i+1, j+1)状态更新而来
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + g[i][j];
        }
    
    cout << dp[1][1];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

2.最长上升子序列

#include 
using namespace std;

#define int long long
const int N = 1e5 + 10;
int dp[N];    // 从第1到第i个数长度为i的数列的严格单调递增的子序列最长长度
int a[N];

int stk[N], tt;    // 模拟栈

// 弱数据 DP
void solve1(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    dp[1] = 1;
    
    int res = 0;
    for(int i = 1; i <= n; i ++){    // 枚举从第1到第i个数的数列
        dp[i] = 1;
        for(int j = 1; j <= i; j ++){    
            if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res, dp[i]);    // 更新答案 防止污染
    }
    cout << res;
}

// 强数据 模拟、贪心
void solve2(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    
    stk[++ tt] = a[1];
    for(int i = 2; i <= n; i ++){
        if(a[i] > stk[tt]) stk[++ tt] = a[i];
        else{    // 替换序列中大于等于a[i]的数
            int id = lower_bound(stk + 1, stk + tt + 1, a[i]) - stk;
            stk[id] = a[i];
        }
    }
    cout << tt;
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve2();
}

3.最长公共子序列

#include 
using namespace std;

#define int long long
typedef pair  PII;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
int dp[N][N]; // a串中1~i字串 与 b串中1~j字串 的最长公共子序列(LCS)的长度

void solve(){
    int n, m;
	string a, b;
    cin >> n >> m >> a >> b;
    a = "#" + a;
    b = "#" + b;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//             cout << dp[i][j] << ' ';
        }
//         cout << 'n';
    }
    cout << dp[n][m];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

4.编辑距离

#include 
using namespace std;

#define int long long
typedef pair  PII;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
int dp[N][N]; // a串中1~i字串 与 b串中1~j字串 的编辑距离(ED, edit distance)最小值
string s[N];

// 得到 a->b 的最短ED 
int get(string a, string b){
    int n = a.size(), m = b.size();
    a = "#" + a;
    b = "#" + b;
    // 初始化：求min
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++) dp[i][j] = INF;
    }
    // 初始化：对于空串变成字符串s的最小ED为 s.length()
    for(int i = 1; i <= n; i ++) dp[i][0] = i;
    for(int i = 1; i <= m; i ++) dp[0][i] = i;
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int f = (a[i] != b[j]);
            dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + f});
        }
    }
//     cout << dp[n][m] << ' ';
    return dp[n][m];
}

void solve(){
    int l, t;
    cin >> l >> t;
    for(int i = 0; i < l; i ++) cin >> s[i];
    while(t --){
        string str;
        int k, res = 0;
        cin >> str >> k;
        for(int i = 0; i < l; i ++){
            if(get(s[i], str) <= k) res ++;
        }
        cout << res << 'n';
    }
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

三、区间DP

石子合并

#include 
using namespace std;

#define int long long
typedef pair  PII;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
int dp[N][N];    // 合并i-j区间的最小代价
int sum[N];    // 前缀和

void solve(){
    int n;
    cin >> n;
    for(int x, i = 1; i <= n; i ++){
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++) dp[i][j] = INF;    //求min 初始化inf
        dp[i][i] = 0;    // 合并一个数代价为0
    }
    
    for(int len = 2; len <= n; len ++)    // 枚举合并区间长度
        for(int l = 1, r = l + len - 1; r <= n; l ++, r ++)    // 枚举左右端点
            for(int k = l; k <= r - 1; k ++){    // 枚举分割点 状态转移
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + (sum[r] - sum[l - 1]));
            }
        
    cout << dp[1][n];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

四、计数类DP

整数划分

#include 
using namespace std;

#define int long long
typedef pair  PII;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;
int dp[N];

void solve(){
    int n;
    cin >> n;
    dp[0] = 1;  // 都不选也为一种方案
    // 完全背包变形求方案数
    for (int i = 1; i <= n; i ++ ){ // 第i个物品体积为i
        for(int j = i; j <= n; j ++){   // 枚举体积 j < i无意义
            dp[j] += dp[j - i]; 
            dp[j] %= mod;
        }
    }
    cout << dp[n];
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

五、数位统计DP

计数问题

#include 
using namespace std;

#define int long long
typedef pair  PII;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;

// 返回1~n中数字x出现的次数
int cnt(int n, int x){
    int res = 0;
    for(int i = 1; i <= to_string(n).size(); i ++){
        int p = pow(10, i - 1);
        int l = n / p / 10, r = n % p;  // 第i位数截得左右边的数
        int d = n / p % 10; // 第i位数
        
        // 四种情况
        if(x) res += l * p;
        if(x == 0 && l) res += (l - 1) * p;
        
        if(x || l){
            if(d == x) res += r + 1;
            if(d > x) res += p;
        }
    }
    return res;
}


void solve(){
	int a, b;
	while(cin >> a >> b && a && b){
	    if(a > b) swap(a, b);
	    for(int i = 0; i <= 9; i ++){
	        cout << cnt(b, i) - cnt(a - 1, i) << ' ';
	    }
	    cout << 'n';
	}
}

signed main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	
	int t = 1;
// 	cin >> t;
	while(t --) solve();
}

六、状态压缩DP

1.蒙德里安的梦想

2.最短Hamilton路径

七、树形DP

没有上司的舞会

八、记忆化搜索

滑雪