HZNUACM寒假集训Day6小结线性DP

线性DP

考虑一组硬币面值 1，5，11 给定W，求凑出W的最少硬币个数

我们记凑出n需要用到的最少硬币数量为f(n) 我们注意到了一个很棒的性质： f(n)只与f(n-1) f(n-5) f(n-11) 有关。

更确切的说f(n)=min(f(n-1),f(n-5),f(n-11)}+1

int f[105], cost;
int main() {
    int n;
    scanf("%d", &n);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        cost = INF;
        if (i - 1 >= 0) cost = min(cost, f[i - 1] + 1);
        if (i - 5 >= 0) cost = min(cost, f[i - 5] + 1);
        if (i - 11 >= 0) cost = min(cost, f[i - 11] + 1);
        f[i] = cost;
        printf("f[%d]=%d\n", i, f[i]);
    }
}

这个做法的原理是：

--f(n)只与f(n-1),f(n-5),f(n-11)相关

--我们只关心f(w)的值，不关心怎么取到W的

这就是DP，将一个问题拆成几个子问题，分别求解这些子问题，即可推断大问题的解

大问题的最优解可以由小问题的最优解推出，这个性质叫“最优子结构性质”。

用DP的情况

--能将大问题拆成小问题

--无后效性

--最优子结构性质

DP核心思想：尽量缩小可能解空间

首先把面对的局面表示为x，称为设计状态

对于状态x，记我们要求出的答案为f(x),目标是求出f(T) 找出f(x)与哪些局面有关，写出一个式子（称为状态转移方程）通过f(p)推出f(x)

最长上升子序列（LIS）

设计状态：记f(x)为以a_{x结尾的LIS长度，那么答案就是max{f(x)}}

状态转移：考虑比x小的每一个p，如果a_x>a_pf(x）可取f(p)+1

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
//LIS
int n;
int a[100], f[100];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int Max;
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        }
        Max = max(Max, f[i]);
    }
    printf("%d", Max);
    return 0;
}

　LCS

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
//LCS
int dp[200][200];
string x, y;
int l1, l2;
int main() {
    cin >> x >> y;
    int l1 = x.length();
    int l2 = y.length();
    for (int i = 1; i <=l1; i++) {
        for (int j = 1; j <=l2; j++) {
            if (x[i-1] == y[j-1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    cout << dp[l1][l2];
    return 0;
}

洛谷P1020 导弹拦截

1.最长不上升序列长度

2.最长上升序列长度

code：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<stack>
#include<cctype>
const double PI = acos(-1.0);
#define eps 1e-6
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

const int maxn = 100010;

int a[maxn], d1[maxn], d2[maxn];
int n;

int main() {
    while (~scanf("%d", &a[n++]));
    int len1 = 0, len2 = 0;
    d1[0] = a[0], d2[0] = a[0];
    for (int i = 1; i < n-1; i++) {
        if (d1[len1] >= a[i]) d1[++len1] = a[i];
        else {
            d1[upper_bound(d1, d1 + len1+1, a[i], greater<int>()) - d1] = a[i];
        }
        if (d2[len2] < a[i]) d2[++len2] = a[i];
        else {
            d2[lower_bound(d2, d2 + len2+1, a[i]) - d2] = a[i];
        }
    }
    //for (int i = 0; i < len1; i++) printf("%d ", d1[i]);
    //for (int i = 0; i < len2; i++) printf("%d ", d2[i]);
    printf("%d\n%d", len1 + 1, len2 + 1);
    return 0;
}

View Code

HZNUACM寒假集训Day6小结 线性DP

HZNUACM寒假集训Day6小结线性DP