算法入门-简单动态规划

BGN64 硬币凑钱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
// Created by XIAOBAI on 2026/5/11.
//
#include <iostream>
#include <algorithm>
//硬币凑钱
using namespace std;
const int N=1e6+10;
int dp[N];
int main() {
    int n;
    cin>>n;
    for (int i=1;i<n;i++) {
        dp[i]=dp[i-1]+1;
        if (i>=5)dp[i]=min(dp[i],dp[i-5]+1);
        if (i>=7)dp[i]=min(dp[i],dp[i-7]+1);
    }
    cout<<dp[n]<<endl;
}

BGN65 小红的地砖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

//
// Created by XIAOBAI on 2026/5/11.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//小红的地砖

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> v(n+1);
    vector<int> dp(n+1);
    for(int i=1;i<n;i++) {
        cin>>v[i];
    }
    dp[1]=v[1];
    dp[0]=v[1];
    for (int i=2;i<=n;i++) {
        dp[i]=min(dp[i-1]+v[i],dp[i-2]+v[i]);
//      cout<<dp[i]<<' ';
    }
    cout<<dp[n];


}

BGN66 最长不下降子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
//最长不下降子序列
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<int> v(n+1);
    vector<int> f(1);
    for(int i=1;i<=n;i++) {
        cin>>v[i];
    }
    f[0]=v[1];
    for (int i=2;i<=n;i++) {
        if (v[i]>=f.back()) f.push_back(v[i]);
        else {
            auto pos=upper_bound(f.begin(),f.end(),v[i]);
            *pos=v[i];
        }
        //       for(auto it:f)cout<<it<<" ";
        //       cout<<'\n';
    }

    cout<<f.size();
}

BGN67 撞车

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
//撞车
using namespace std;
int main() {
    map<int,int> mp;
    int n;
    cin>>n;
    vector<int> v;
    vector<int> f(1);
    for (int i=1;i<=n;i++) {
        int temp1,temp2;
        cin>>temp1>>temp2;
        mp[temp1]=temp2;
    }
    for (auto i:mp) {
        v.push_back(i.second);
    }

    f[0]=v[0];
    for (int i=1;i<n;i++) {
        if (v[i]>=f.back()) f.push_back(v[i]);
        else {
            auto pos=upper_bound(f.begin(),f.end(),v[i]);
            *pos=v[i];
        }
        //       for(auto it:f)cout<<it<<" ";
        //       cout<<'\n';
    }
    // for (auto i:f) {
    //     cout<<i<<" ";
    // }
    cout<<n-f.size();
}

BGN68 最大子段和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll=long long int;
//最大子段和
int main() {
    int n;
    cin>>n;
    vector<ll> v(n);
    vector<ll> f(n);
    for(int i=0;i<n;i++) {
        cin>>v[i];
    }
    if (n==1) {
        cout<<v[0];
        return 0;
    }
    f[0]=v[0];
    ll M=-2e9;
    for(int i=1;i<n;i++) {
        f[i]=max(v[i]+f[i-1],v[i]);
        M=max(M,f[i]);
    }
    cout<<M;
}

BGN70 【模板】01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//
// Created by XIAOBAI on 2026/5/12.
//
//【模板】01背包
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
int main () {
    ios_base::sync_with_stdio (false);
    cin.tie (0);
    int n,V;
    cin >> n >> V;
    vector<int> w(n+1),s(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> s[i];
    }
    vector<vector<int>> dp(n+1,vector<int>(V+1,0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (w[i]>j) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+s[i]);
        }
        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= V; j++) {
        //         cout << dp[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        // cout << endl;
    }
    cout<<dp[n][V]<<'\n';
    vector<vector<int>> dp1(n+1,vector<int>(V+1,-INF));
    for (int i = 0; i <= n; i++) {
        dp1[i][0]=0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= V; j++) {
            if (w[i]>j) dp1[i][j]=dp1[i-1][j];
            else dp1[i][j]=max(dp1[i-1][j],dp1[i-1][j-w[i]]+s[i]);
        }
        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= V; j++) {
        //         cout << dp1[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        // cout << endl;
    }
    if (dp1[n][V]<0) cout<<"0";
    else cout<<dp1[n][V]<<'\n';



    

}