AcWing算法提高课

Created in March 31, 2025

2025   ·   code   algorithm   acwing   算法提高课   ·   learning-notebook

动态规划

最长上升子序列模型

拦截导弹

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N], f[N], g[N];
// 使用两次动态规划解决问题
// 集合表示：f[i]
// 含义：前i个元素中最长非增序列的长度
// 性质：最大值
// 集合计算
// 依次遍历j，a[j] >= a[i]，那么就有可能构成最长非增序列，但还要自己所在的非增序列进行比较
// f[i] = max(f[j] + 1, f[i])
// 最开始初始化f[i] = 1，因为自己也可以构成一个序列
// 集合表示：h[i]
// 含义：前i个元素中最长递增序列的长度
// 性质：最大值
// 集合计算：
// 如果a[j] < a[i]，并且j < i，那么同一个导弹系统肯定无法同时拦截i和j两者
// h[i] = max(h[i], h[j] + 1)
// 序列的长度就是最少需要导弹系统的数量

int main(){
    n = 1;
    while(cin >> a[n])
        n ++;
    n --;

    a[0] = 30010;
    for(int i = 1; i <= n; i ++){
        // f[i] = 1;
        g[i] = 1;
        for(int j = 0; j < i; j ++)
            if(a[j] >= a[i])
                f[i] = max(f[i], f[j] + 1);
            else
                g[i] = max(g[i], g[j] + 1);

    }

    // 注意一定要显示定义答案为0！！！
        int ans1 = 0, ans2 = 0;

    for(int i = 1; i <= n; i ++){
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }

    cout << ans1 << endl;
    cout << ans2 << endl;

    return 0;
}

导弹防御系统

// 该问题的关键是如何将其转化为LIS问题
// LIS问题的关键是每个新遍历到的元素只需要和序列的最后一个元素进行比较即可确定是否可以加入序列或者创建新的序列
// 而这道题又有上升又有下降，是在是无法判断
// 只能通过dfs来判断每一种状态
// 剪枝条件
// 如果导弹系统总数大于等于当前ans，停止
// 如果已经遍历到最后一个导弹，判断是否更新ans，停止
// 我们定义数组up[N]和down[N]分别来记录第i个上升或者下降的导弹系统的最后一个元素
// 并将新的元素和他们进行比较
// 下面使用的贪心的思想
// 对于上升的导弹系统，我们遍历到第一个序列最后一个元素高度小于当前元素高度的
// 并将这个序列的最后一个元素高度更新为当前元素高度
// 如果都没有找到，就新创建一个上升的导弹系统记录
// 根据这个规则，我们发现up数组就是递增的，这也是为什么遍历到第一个序列最后一个元素高度小于当前元素高度的就进行更新的原因，距离这个元素最近（贪心），节约那些差距更大的，留给其他元素
// 下降的导弹系统则是遍历到第一个序列最后一个元素高度大于当前元素高度的
// 余下同理
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
int h[N], up[N], down[N];
int n, ans;

void dfs(int u, int d, int t){
    if(u + d >= ans)
        return ;
    if(t == n){
        if(u + d < ans)
            ans = u + d;
        return ;
    }
    int i;
    // 上升的导弹系统
    for(i = 1; i <= u; i ++){
        if(up[i] < h[t])
            break;
    }
    int temp = up[i];
    up[i] = h[t];
    dfs(max(i, u), d, t + 1);
    up[i] = temp;
    for(i = 1; i <= d; i ++)
        if(down[i] > h[t])
            break;
    temp = down[i];
    down[i] = h[t];
    dfs(u, max(d, i), t + 1);
    down[i] = temp;
}

int main(){
    while(cin >> n && n){
        ans = INT_MAX;

        for(int i = 0; i < n; i ++)
            cin >> h[i];

        // 上升的导弹系统，下降的导弹系统，当前第几颗导弹
        dfs(0, 0, 0);

        cout << ans<< endl;
    }
    return 0;
}

背包模型

宠物小精灵之收服

知识点

解题思路

  • 本题经过分析：
    • 花费1：精灵球数量
    • 花费2：皮卡丘体力值
    • 价值：小精灵的数量
双重价值背包
  • 状态表示：
    • f[i][j][k]表示所有只从第i个物品中选，且花费1不超过j，花费2不超过k。
  • 状态计算：
    • f[i][j][k] = max(f[i][j][k], f[i - 1][j - v1[i]][k - v2[i]])

实现代码

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

const int N = 1010, M = 510;
int n, V1, V2;
int f[N][M];

int main(){
    cin >> V1 >> V2 >> n;
    for(int i = 1; i <= n; i ++){
        int v1, v2;
        cin >> v1 >> v2;
        for(int j = V1; j >= v1; j --)
            for(int k = V2; k > v2; k --)
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }

    int k = V2;

    while(k > 0 && f[V1][k] == f[V1][V2])
        k --;

    cout << f[V1][V2] << " " << V2 - k << endl;
    return 0;
}

数字组合

实现代码

// 状态表示f[i][j]
// 集合表示：遍历到第i个数，和为j的方案数
// 属性：数量
// 状态计算
// f[i][j] = f[i - 1][j] + f[i - 1][j - a[i]]
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int f[N][M];
int a[N];


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

    f[0][0] = 1;

    int res = 0;

    for(int i = 1; i <= n; i ++){
        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;


}

买书

知识点

解题思路

  • 动态规划:
    • 状态表示
      • 集合：所有只从前i个物品中选，并且总体积恰好是j的方案数
      • 属性：Count
    • 状态计算：
      • f[i][j] = f[i - 1][j]
      • f[i][j] += f[i - 1][j - v*1] + f[i - 1][j - v*2] + ...

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int v[5] = {0, 10, 20, 50, 100};
int f[N];

int main(){
    int m;
    cin >> m;
    f[0] = 1;
    for(int i = 1; i <= 4; i ++){
        for(int j = 0; j <= m; j ++){
            if(j >= v[i])
                f[j] += f[j - v[i]];
        }
    }

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

货币系统

实现代码

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

const int N = 3010;

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


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

    f[0] = 1;

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

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

货币系统(难)

知识点

  • 完全背包问题

解题思路

  • 状态表示f[i][j]
    • 集合：用前i种类硬币，组成数值为j的硬币
    • 属性：能够表示出数值为j的硬币，bool
  • 状态计算
    • 可以分为若干个集合
      • 用0个第i类硬币
      • 用1个第i类硬币
      • …
      • 用 k 个第i类硬币
  • 进行循环时，首先判断该硬币是否已经能表示，如果已经能被表示，则跳过

实现代码

// 状态表示f[i][j]
// 集合：用前i种类硬币，组成数值为j的硬币
// 属性：能够表示出数值为j的硬币，bool
// 状态计算
// 可以分为若干个集合
// 用0个第i类硬币
// 用1个第i类硬币
// 。。。
// 用 k 个第i类硬币
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 25010;
int tt = 0;
int a[N];
bool f[M];


int main(){
    cin >> tt;
    while(tt --){
        memset(f, 0, sizeof f);
        memset(a, 0, sizeof a);
        int n;
        cin >> n;
        for(int i = 1; i <= n; i ++){
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int m = a[n];
        f[0] = 1;

        int res = 0;

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

    }
    return 0;
}

状态机模型

股票买卖 IV

// 状态表示：f[i][j][k]
// 含义：前i个物品中，已进行了（包括正在进行的）j次交易，k = 0, 1；0表示货已出手，1表示货还在手，能够收获的最大利润
// 性质：最大值
// 状态计算：
// f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i])
// f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i])

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

const int N = 100010, M = 110;
int f[N][M][2], n, m, w[N];
int main(){
    cin >> n >> m;
    memset(f, - 0x3f, sizeof f);
    for(int i = 1; i <= n; i ++)
        cin >> w[i];
    
    for(int i = 0; i <= n; i ++)
        f[i][0][0] = 0;
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
    }
    
    int res = 0;
    for(int i = 0; i <= m; i ++)
        res = max(res, f[n][i][0]);
        
    cout << res << endl;
    
    return 0;
}


Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Google Gemini updates: Flash 1.5, Gemma 2 and Project Astra
  • Displaying External Posts on Your al-folio Blog
  • 强化学习导论
  • 企业项目实训
  • 面试总结