动态规划

Skyzhou666 · 2022-07-23 11:14:21 · 算法·理论

关于动态规划

线性DP

最长上升子序列LIS（n^2）

dp[x]表示以a[x]为结尾的最长上升子序列，将求n个数的LIS转化为n-1个数的LIS，以此类推

#include <iostream>
#define MAXN 1001
using namespace std;

int a[MAXN], dp[MAXN];

int main()
{
    int n;
    cin >> n;
    for(int x = 0; x < n; x++) cin >> a[x];
    dp[0] = 1;
    for(int x = 0; x < n; x++)
        for(int y = 0; y < x; y++)
            if(a[y] < a[x]) dp[x] = max(dp[x], dp[y]+1);
    int ans = 0;
    for(int x = 0; x < n; x++) ans = max(ans, dp[x]);
    cout << ans << endl;
    return 0;
}

dp[x]表示上升子序列长度为x的序列的最小末尾数值，因为这个dp是单调的，所以在改变最小末尾数值时可以用二分，使得时间复杂度变为$nlogn

#include <iostream>
#define MAXN 1001
#define INF 0x7fffffff
using namespace std;

int a[MAXN], dp[MAXN];

int main()
{
    int n;
    cin >> n;
    for(int x = 0; x < n; x++)
    {
        cin >> a[x];
        dp[x] = INF;
    }
    int ans = 1;
    dp[0] = 0;
    for(int x = 0; x < n; x++)
    {
        int l = 0, r = ans, mid;
        if(a[x] > dp[ans]) dp[++ans] = a[x];
        else
        {
            while(l < r)
            {
                mid = (l + r) >> 1;
                if(dp[mid] > a[x]) r = mid;
                else l = mid + 1;
            }
            //cout << x << " " << l << endl;
            dp[l] = min(a[x], dp[l]);
        }
    }
    cout << ans << endl;
    return 0;
}

最长公共子序列LCS（n^2）

dp[i][j]表示前缀子串a[1~i]和b[1~j]的最长公共子序列长度

#include <iostream>
#define MAXN 1001
using namespace std;

int a[MAXN], b[MAXN], dp[MAXN][MAXN];

int main()
{
    int n;
    cin >> n;
    for(int x = 1; x <= n; x++) cin >> a[x];
    for(int x = 1; x <= n; x++) cin >> b[x];
    for(int x = 1; x <= n; x++)
    {
        for(int y = 1; y <= n; y++)
        {
            dp[x][y] = max(dp[x-1][y], dp[x][y-1]);
            if(a[x] == b[y]) dp[x][y] = max(dp[x][y], dp[x-1][y-1]+1);
        }
    }
    cout << dp[n][n] << endl;
    return 0;
}

线性dp

01背包

P1048 采药（01背包模板题）

#include <iostream>
using namespace std;

int dp[1001], t[1001], v[1001];

int main()
{
    int T, M;
    cin >> T >> M;
    for(int x = 0; x < M; x++) cin >> t[x] >> v[x];

    //关键在这两行
    for(int x = 0; x < M; x++)
        for(int y = T; y >= t[x]; y--)
            dp[y] = max(dp[y], dp[y-t[x]]+v[x]);

    cout << dp[T] << endl;
    return 0;
}

_dp_i代表在i这个时间内可以采到草药的最大总价值。_

第一层循环遍历每颗草药，代表对第i颗药做规划，第二层循环则是用采第i颗药的时间对dp进行更新，从最大时间开始遍历到采这颗药的时间（倒序是因为如果从正序的话后面的不断更新前面的，导致一颗药采多次，但这是01背包，每颗药只有采或者不采，故矛盾），这段时间内都能采这颗药，并且通过状态转移方程来比较原来这个时间内采到草药的价值和采这颗药能获得的价值并取其最大值，这样不断更新下去最后得到的每个dp_i都是i时间内的最大总价值。

01背包中的方案数问题（弱化版）

现在有n个物品给出每个物品的大小w_i，将其刚好塞入容量为m的背包，有多少种方案？

#include <iostream>
#define MAXN 1001
using namespace std;

int dp[MAXN], a[MAXN];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int x = 0; x < n; x++) cin >> a[x];
    dp[0] = 1;
    for(int x = 0; x < n; x++)
        for(int y = m; y >= a[x]; y--) dp[y] += dp[y-a[x]];
    cout << dp[m] << endl;
    return 0;
}

完全背包

~~哈哈不过就是01背包把倒序改成正序罢了刚才瞎调试的时候试出来了（（~~

P1616 疯狂的采药（完全背包模板题）

#include <iostream>
using namespace std;

long long f[10000001], tm[10001], val[10001];

int main()
{
    int t, n;
    cin >> t >> n;
    for(int x = 0; x < n; x++) cin >> tm[x] >> val[x];
    for(int x = 0; x < n; x++)
        for(int y = tm[x]; y <= t; y++)
            f[y] = max(f[y], f[y-tm[x]] + val[x]);
    cout << f[t] << endl;
    return 0;
}

思路和上题一样，只不过第二层循环遍历时是正序，因为每颗药可以无限次采摘，只要能限定时间内最大价值填满就行。卡long long（