动态规划入门

动态规划入门

题目一

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


const int N = 1e5+10;

int n,T;
int res[N];
int home[N];
int main () {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1;i <= n;i++) {
            cin >> home[i];
        }
        memset(res,0,sizeof res);
        for (int i = n;i >= 1;i--) {
            res[i] = max(res[i+1],res[i+2]+home[i]);
        }
        cout << res[1];
    }
}

题目二

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


const int N = 1e3+10;

int home[N][N];
int ans[N][N];

int r;
int main () {
    cin >> r;
    for (int i = 1;i <= r;i++) {
        for (int j = 1;j <= i;j++) {
            cin >> home[i][j];
        }
    }
    for (int i = r;i>=1;i--) {
        for (int j = 1;j <= i;j++) {
            ans[i][j] = max(ans[i+1][j]+home[i][j],ans[i+1][j+1]+home[i][j]);
        }
    }
    cout << ans[1][1];
}

题目三

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


const int N = 1e3+10;

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 = 0;j <= m;j++) {
            if (j < v[i]) {
                f[i][j] = f[i-1][j];
            }else {
                f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i]);
            }
        }
    }
    cout << f[n][m];
}