「kuangbin带你飞」专题十二 基础DP

Posted by StandHR on August 19, 2018
View times

更新中

传送门

A.HDU1024 Max Sum Plus Plus

状态:$dp[i][j]$前$j$个数分成$i$组和的最大值。
决策:第$j$个数 计入第$i$组 VS 自己成新组。
方程:$dp[i][j]=max(dp[i][j-1]+S[j],max(dp[i-1][k])+a[j]),\; \; k\in[i-1,j)$
用Max数组将上一层的$max(dp[i-1][k]),\; \; k\in[i-1,j)$值记录下来,复杂度$n^2$

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int S[maxn], dp[maxn], Max[maxn];

int main() {
    int m, n;
    while (~scanf("%d%d", &m, &n)) {
        memset(dp, 0, sizeof(dp));
        memset(Max, 0, sizeof(Max));
        for (int i = 1; i <= n; i++) {
            scanf("%d", &S[i]);
        }
        int ans;
        for (int i = 1; i <= m; i++) {
            ans = -INF;
            for (int j = i; j <= n; j++) {     //至少i数才能分i组
                dp[j] = max(dp[j - 1] + S[j], Max[j - 1] + S[j]);
                Max[j - 1] = ans;
                ans = max(ans, dp[j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B.HDU1029 Ignatius and the Princess IV

这题很多方法。只要输出所有数中出现次数最多的数就行。

B.1.sort

把所有数排序后,最中间的元素就是结果。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1000010;
int a[maxn];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        printf("%d\n", a[(n + 1) / 2]);
    }
    return 0;
}

B.2.打表

用hash表记录每个数出现的次数,输出次数最多的数。

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1000010;
int num[maxn];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        memset(num, 0, sizeof(num));
        int ans = 0, tmp = 0;
        while (n--) {
            int x;
            scanf("%d", &x);
            num[x]++;
            if (num[x] > tmp) {
                tmp = num[x];
                ans = x;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B.3.思维

只有最终结果个数会大于等于$\frac{n}{2}$,也就是$ans$的个数-其它数个数$\geq$0,于是用$num$计数。
当$num=0$时,把当前数$x$假设为最终结果$ans$,$num$++。
当$x=ans$时,$num$++。
当$x\neq ans$时,$num$--。
遍历一次后,最后的$ans$即为所求。

#include <cstdio>
using namespace std;

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int ans, num = 0;
        while (n--) {
            int x;
            scanf("%d", &x);
            if (num == 0) {
                ans = x;
                num++;
                continue;
            }
            if (x == ans) {
                num++;
            } else {
                num--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C.HDU1069 Monkey and Banana

每个方块当作6种方块,按长、宽排序。 状态:$dp[i]$前$i$个木块最高值。
决策:取了前$j(j<i)$个方块后取方块$i$
方程:$dp[i]=max(dp[i],dp[j]+V[i].z),(j<i)$

注意加上判断$V[j].x>V[i].x \text{ && } V[j].y>V[i].y$,来避免当前方块$i$的长或宽和第$j$个方块相等

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back

const int INF = 0x3f3f3f3f;
struct node {
    int x, y, z;
    node() {}
    node(int x, int y, int z) : x(x), y(y), z(z) {}
    bool operator < (const node &r) const {
        if (x == r.x)
            return y > r.y;
        return x > r.x;
    }
};
vector<node> V;
int dp[1100];

int main() {
    int n, Case = 0;
    while (~scanf("%d", &n) && n) {
        V.clear();
        memset(dp, 0, sizeof(dp));
        while (n--) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            V.pb(node(x, y, z));
            V.pb(node(x, z, y));
            V.pb(node(y, x, z));
            V.pb(node(y, z, x));
            V.pb(node(z, x, y));
            V.pb(node(z, y, x));
        }
        sort(V.begin(), V.end());
        int ans = 0;
        for (int i = 0; i < (int)V.size(); i++) {
            dp[i] = V[i].z;
            for (int j = 0; j < i; j++) {
                if (V[j].x > V[i].x && V[j].y > V[i].y) {
                    dp[i] = max(dp[i], dp[j] + V[i].z);
                }
            }
            ans = max(dp[i], ans);
        }
        printf("Case %d: maximum height = %d\n", ++Case, ans);
    }
    return 0;
}