526互联

nefu-dp1 （线性dp）

发布时间 2023-08-02 17:48:15作者: Sakana~

nefu-dp1

https://vjudge.csgrandeur.cn/contest/571200#overview
感谢z神的题单
dp废物来打基础了。
(感觉难度大概是递减的)

琪露诺

单调队列优化dp

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int f[N], a[N], n, l, r; //f[i]:i结尾的最大值

int main () {
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++)    cin >> a[i];
    queue<int> q; //单调队列优化dp
    memset (f, -0x3f, sizeof f);
    f[0] = a[0];
    q.push (0);
    for (int i = l; i <= n; i++) {
        while (!q.empty () && f[q.front ()] < f[i-l])   q.pop ();
        q.push (i - l);
        while (!q.empty() && q.front () < i - r)    q.pop ();
        f[i] = f[q.front ()] + a[i];
    }
    int ans = f[n];
    for (int i = 1; i < r; i++)    ans = max (ans, f[n-i]);
    cout << ans << endl;
}

护卫队

要用到一个dp辅助数组，提前预处理！

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1005;
const double inf = 1e18;
ll n, s, W, w[N];
double f[N], t[N][N], tt[N]; //f[i]: 前i辆车通过的最短时间, t[i][j]: i-j位一车队的通过时间

int main () {
    cin >> W >> s >> n;
    for (int i = 1; i <= n; i++) {
        f[i] = inf;
        for (int j = 1; j <= n; j++) {
            t[i][j] = inf;
        }
    }
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> w[i] >> x;
        tt[i] = 1.0 * s / x * 60;
        t[i][i] = tt[i];
        w[i] += w[i-1];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            t[i][j] = max (t[i][j-1], tt[j]);
            //cout << t[i][j] << ' ';
        }
        //cout << endl;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (w[i] - w[j-1] > W)  continue;
            f[i] = min (f[i], f[j-1] + t[j][i]);
        }
    }
    cout << fixed << setprecision (1) << f[n];
}

书的复制

重点在于方案输出，pre数组记录

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 505;
int n, m, pre[N];
ll a[N], s[N], f[N][N]; //f[i][j]: 考虑到第i人,划分了j组的最小抄写时间

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

    for (int i = 1; i <= n; i++) {
        int id = 0;
        for (int j = 1; j <= min (i, m); j++) {
            for (int k = 1; k < i; k++) {
                f[i][j] = min (f[i][j], max (f[k][j-1], s[i] - s[k]));
            }
            //cout << f[i][j] << ' ';
        }
        //cout << endl;
    }
    //cout << f[n][m] << endl;
    int s = 0, w = n;
	for(int i = n; i >= 1; i--){//这里贪心，因为后面的人抄尽量多，前面少，所以倒过来枚举
		s += a[i];
		if (s > f[n][m])    s = a[i], pre[w] = i + 1, w = i;//pre[w]记录这个人抄书的开始位置
	}
	cout << 1 << ' '  << w << endl;//第一组特判
    //output (n);
    //for (int i = 1; i <= n; i++)    cout << pre[i] << ' ';
    for (int i = 1; i <= n; i++) {
        if (pre[i])     cout << pre[i] << ' ' << i << endl;
    }
}

摆花

重点在方案涉及，二维即可

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 105, mod = 1e6 + 7;
int n, m, a[N];
ll f[N][N]; //f[i][j]: 前i种花盆摆了j个的方案数

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) { //该种花也可以一个都不摆
            for (int k = 0; k <= min(j, a[i]); k++) {
                (f[i][j] += f[i-1][j-k]) %= mod;
            }
        }
    }
    cout << f[n][m] << endl;
}

导弹拦截

二分优化求LIS

    #include <bits/stdc++.h>

    using namespace std;
    const int N = 1e5 + 5;
    int a[N], f[N]; //f[i]: 长度为i的结尾最大值

    int main () {
        int n = 0, x, len;
        while (cin >> x)    a[++n] = x;
        
        f[1] = a[1], len = 1;
        for (int i = 2; i <= n; i++) {
            if (a[i] <= f[len])     f[++len] = a[i];
            else {
                int l = 1, r = len;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (f[mid] < a[i])  r = mid;
                    else    l = mid + 1;
                }
                f[r] = a[i];
            }
        }
        //for (int i = 1; i <= len; i++)  cout << f[i] << ' ';
        cout << len << endl;

        //不升序列个数等于最长上升序列长度
        f[1] = a[1], len = 1;
        for (int i = 1; i <= n; i++) {
            if (a[i] > f[len])      f[++len] = a[i];
            else {
                int l = 1, r = len;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (f[mid] >= a[i]) r = mid;
                    else    l = mid + 1;
                }
                f[l] = a[i];
            }
        }
        //for (int i = 1; i <= len; i++)  cout << f[i] << ' ';
        cout << len << endl;

    }

开心的金明

萌萌题

    #include <bits/stdc++.h>
    #define ll long long

    using namespace std;
    const int N = 3e4 + 5, M = 30, mod = 1e6 + 7;
    int n, m;
    ll f[M][N], ans; //f[i][j]: 前i个物品剩j元的最大价值

    int main () {
        cin >> m >> n;
        for (int i = 1; i <= n; i++) {
            int a, b;
            cin >> a >> b;
            for (int j = m; j >= 0; j--) {
                f[i][j] = f[i-1][j];
                if (j - a >= 0)    f[i][j] = max (f[i-1][j], f[i-1][j-a] + 1ll * a * b);
            }
        }
        for (int i = 0; i <= m; i++)    ans = max (ans, f[n][i]);
        cout << ans << endl;
    }

小A点菜

萌萌题

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 105, M = 10005;
int n, m, a;
ll f[N][M]; //f[i][j]: 前i个菜剩j元的方案

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

砝码称重

萌萌题

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 10005;
int a[] = {1, 2, 3, 5, 10, 20}, ans, x;
bool f[N];

int main () {
    f[0] = 1;
    for (int i = 0; i < 6; i++) {
        cin >> x;
        for (int j = 1000; j >= 0; j--) {
            for (int k = x; k > 0; k--) {
                f[j + k * a[i]] |= f[j];
            }
        }
    }
    // for (int i = 0; i <= 1000; i++) {
    //     if (f[i])   cout << i << endl;
    // } 
    for (int i = 1; i <= 1000; i++)     ans += f[i];
    cout << "Total=" << ans << endl;
}