kuangbin dp 基础DP1

　

dp1

kuangbin dp 基础DP1

1.Max Sum Plus Plus

这题比较坑，m的取值范围没给，但是O(mn)是可以过的

dp[i,j] = max(dp[i,j-1], max(dp[i-1,k]))+a[i]
dp[i,j]，前j个组i组
优化一维

#include <iOStream>
#include <cstring>
#include <cstdio>

using namespace std;

#define D 1000000

int a[D + 5];
int dp[D + 5];
int MAX[D + 5];

int max(int a, int b) {
    return a > b ? a : b;
}

int main()
{
    int m, n;
    int mmax;
    while (cin >> m >> n) {
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        memset(MAX, 0, sizeof(MAX));
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= m; i++) {
            mmax = -2000000000;
            MAX[i - 1] = mmax;
            for (int j = i; j <= n; j++) {
                dp[j] = max(dp[j - 1], MAX[j - 1]) + a[j];
                MAX[j - 1] = mmax;
                mmax = max(mmax, dp[j]);
            }
        }
        cout << mmax << endl;
    }

    return 0;
}

2.Ignatius and the Princess IV

这题很奇怪，我用map就过了，他为什么要标dp，而且由于固有思路，一直想不出来dp要怎么写，看了题解，题解说得很麻烦，总之就是，反正我最大，那我剪掉你们所有的数还会有1，所以我牛逼

cin >> t;
if (result == t){
    cnt++;
}
else {
    cnt--;
    result = t;
}

3.Monkey and Banana

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define mem(a) memset(a, 0, sizeof(a))

typedef struct {
    int x, y, z;
} rec;

rec a[200];
int dp[200][200];

void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}

int max(int a, int b) {
    return a > b ? a : b;
}

bool comparison(rec a, rec b) {
    if (a.x > b.x)
        return true;
    else if (a.x < b.x)
        return false;
    else if (a.y > b.y)
        return true;
    else
        return false;
}

int main()
{
    int n;
    int t = 0;
    cin >> n;
    while (n) {
        ++t;
        mem(a);
        mem(dp);
        for (int i = 0; i < n * 3; i += 3) {
            cin >> a[i].x >> a[i].y >> a[i].z;
            a[i + 1] = a[i];
            a[i + 2] = a[i];
            swap(a[i + 1].x, a[i + 1].z);
            swap(a[i + 2].y, a[i + 2].z);
            if (a[i].x < a[i].y)
                swap(a[i].x, a[i].y);
            if (a[i + 1].x < a[i + 1].y)
                swap(a[i + 1].x, a[i + 1].y);
            if (a[i + 2].x < a[i + 2].y)
                swap(a[i + 2].x, a[i + 2].y);
        }
        n *= 3;
        sort(a, a + n, comparison);

        int maxx = 0;
        for (int i = 0; i < n; i++)
            dp[0][i] = a[i].z;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < j; k++) {
                    if (a[k].x > a[j].x && a[k].y > a[j].y)
                        dp[i][j] = max(dp[i-1][k], dp[i][j]);
                }
                dp[i][j] += a[j].z;
                maxx = max(dp[i][j], maxx);
            }
        }
        printf("Case %d: maximum height = %d\n", t, maxx);
        cin >> n;
    }
}

4.免费馅饼

f[i][j] = max(f[i-1][j-1], f[i][j-1], f[i+1][j]) + a[i][j]

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int a[100005][12] = { 0 };
int b[100005][12] = { 0 };

int max(int a, int b) {
    return a > b ? a : b;
}

int main()
{
    int n;
    cin >> n;
    while (n) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int sum = 0;
        int maxy = 0;
        int x, y;
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &x, &y);
            b[y][x + 1]++;
            maxy = max(maxy, y);
        }
        for (int i = 1; i <= maxy; i++)
            for (int j = 1; j <= 11; j++) {
                if (abs(6 - j) > i)
                    ;
                else
                    a[i][j] = b[i][j] + max(max(a[i - 1][j - 1], a[i - 1][j]), a[i - 1][j + 1]);
            }
        for (int i = 1; i <= 11; i++)
            sum = max(sum, a[maxy][i]);
        cout << sum << endl;
        cin >> n;
    }

    return 0;
}

5.最少拦截系统

#include <iostream>
#include <cstring>

using namespace std;

int a[40000] = { 0 };

int main()
{
    int n, t, maxx = 0, j, sum;
    while (cin >> n) {
        memset(a, 0, sizeof(a));
        sum = 0;
        maxx = 0;
        for (int i = 0; i < n; i++) {
            cin >> t;
            if (t > maxx) {
                a[t] = 1;
                maxx = t;
            }
            else {
                j = t;
                while (!a[j])
                    ++j;
                a[j]--;
                if (maxx == j && !a[j])
                    maxx = t;
                a[t]++;
            }
        }
        for (int i = 0; i <= 30000; i++)
            sum += a[i];
        cout << sum << endl;
    }

    return 0;
}

6.Doing Homework

这题一开始以为是贪心，还觉得这数据量好傻逼，后来没找到贪心策略，觉得一定是我自己太菜了，结果发现根本就不是贪心，这题是dp，还tm的是状压dp

这题的状态转移有点简单粗暴，基本上和暴力差不多，就不写转移方程了，但是记录路径、字典序是这题的两个小细节，还是要妥善处理的

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

#define ll long long
#define D 1 << 15 + 1
#define mem(a) memset(a, 0, sizeof(a))
#define MAX 1 << 25

typedef struct {
    int d, t;
} kemu;

typedef struct {
    int v, t;
} DP;

string s[20];
kemu a[20];
DP dp[D];
int pre[D];
int n;

int f(int k) {
    if (dp[k].v < MAX)
        return dp[k].v;
    for (int i = 0; i < n; i++) {
        //如果第i位是1的话
        int m = 1 << i;
        if (k & m) {
            //第i未变成0
            m ^= k;
            int value;
            f(m);
            if (dp[m].t + a[i].t < a[i].d)
                value = 0;
            else
                value = a[i].t + dp[m].t - a[i].d;
            //用'='来使字典序最小，因为题目给出的输入是按字典序排的，没有这个条件可以快排一下
            if (dp[k].v >= dp[m].v + value) {
                dp[k].v = dp[m].v + value;
                dp[k].t = dp[m].t + a[i].t;
                //记录路径
                pre[k] = m;
            }
        }
    }
    return dp[k].v;
}

void output(int m) {
    if (m) {
        output(pre[m]);
        for (int i = 0; i < n; i++) {
            if ((m ^ (1 << i)) == pre[m])
                cout << s[i] << endl;
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        dp[0].v = 0;
        dp[0].t = 0;
        cin >> n;
        for (int i = 1; i < (1 << n); i++) {
            dp[i].v = MAX;
        }
        for (int i = 0; i < n; i++) {
            cin >> s[i] >> a[i].d >> a[i].t;
        }
        int m = (1 << n) - 1;
        cout << f(m) << endl;
        output(m);
    }
}

7.Super Jumping! Jumping! Jumping!

这题实际上就是最大递增序列和

dp[i][j]：第j个数是第i个递增数
dp[i][j] = max(dp[i-1][k]) + a[j];

​ 然后顺着这个思路，我一直在想该怎么把k优化掉，想了各种奇奇怪怪的方法还是办不到，没办法还是看了题解

​ 结果！！！！

​ 我发现我可能是个傻子，第一维屁用没有！！！

​ 而我居然这么久都没有发现。。。我可能是思维江化了吧。。。

​ GG

dp[i] = max(dp[k]) + a[j];

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;

#define ll long long
#define mem(a) memset(a, 0, sizeof(a))

ll a[2000];
ll dp[2000];

ll max(ll a, ll b) {
    return a > b ? a : b;
}

int main()
{
    int n;
    cin >> n;
    while (n) {
        mem(dp);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            dp[i] = a[i];
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i])
                    dp[i] = max(dp[j] + a[i], dp[i]);
            }
        }
        ll maxx = 0;
        for (int i = 0; i < n; i++) {
            maxx = max(maxx, dp[i]);
        }
        cout << maxx << endl;
        cin >> n;
    }
}

8.Piggy-Bank

这题实际上是背包问题，背包空间’F-E’，N件物品，每件物品重W价值P，问塞满背包的最小价值（物品不可拆）

dp[j] = min(dp[j], dp[j-w[i]] + p[i])

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;
#define D 0x7f7f7f7f

int dp[20000];
int w[1000], p[1000];

int min(int a, int b) {
    return a < b ? a : b;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n, E, F;
        cin >> E >> F;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> p[i] >> w[i];
        }
        memset(dp, 0x7f, sizeof(dp));
        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = w[i]; j <= F - E; j++) {
                dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
            }
        }
        if (dp[F - E] < D) {
            printf("The Minimum amount of money in the piggy-bank is %d.\n", dp[F - E]);
        }
        else {
            cout << "This is impossible." << endl;
        }
    }
}

9.tickets

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

using namespace std;
#define D 0x7f7f7f7f

int a[3000];

int min(int a, int b) {
    return a < b ? a : b;
}

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        a[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 2; i <= n; i++) {
            int t;
            cin >> t;
            a[i] = min(a[i - 2] + t, a[i - 1] + a[i]);
        }
        int hour = 8, minu = 0, seco = 0;
        seco = a[n] % 60;
        a[n] /= 60;
        minu = a[n] % 60;
        a[n] /= 60;
        hour += a[n];
        char s[] = "am";
        if (hour > 12) {
            hour -= 12;
            s[0] = 'p';
        }
        printf("%02d:%02d:%02d %s\n", hour, minu, seco, s);
    }
}

10.FatMouse’s Speed

这题其实就是最大递减序列，只不过体重可能相同，所以不能用最大递减序列的O(nlogn)来做，得用O(n^2)，然后记录路径就好

11.Jury Compromise

相关阅读

网站建设必须建立在用户体验的基础之上

　　峰终定律，是针对用户而言的，具体而言，就是用户对某个产品的体验，是有记忆点的，包括两个，一个是高峰点，另一个是离开时的记忆点，比如

数据库学习的一些基础知识及常用命令

数据库 “数据库”是以一定方式储存在一起、能够多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。 【基本

Windows远程时无法复制文件--杀进程rdpclip.exe，然后再

1.远程登陆到主机上2.任务管理器杀进程rdpclip.exe3.【开始】，搜索rdpclip.exe，点击运行此时重新复制文件，可以跨主机复制啦原以为是

统计学中的协方差矩阵（阵列信号基础）

在处理阵列信号的时候，为了获得空间信号维度的相关性，以估计目标的信息。故使用协方差矩阵能够获得这些，因为协方差矩阵是每一维度下

Amazon的云计算（1）——基础存储架构Dynamo

Amazon 依靠在电子商务中积累的大量基础性设施和各类先进技术，很早地进入了云计算领域，并在提供计算、存储等服务方面处于领先地位