头像

在下是个废物




离线:16小时前


最近来访(19)
用户头像
TheGiao
用户头像
INnoVation
用户头像
zombotany
用户头像
knighz
用户头像
fighting_HZ
用户头像
看海的人
用户头像
狐闹
用户头像
来夕
用户头像
牛马王子
用户头像
木棉觉
用户头像
zyn酱

活动打卡代码 LeetCode 384. 打乱数组

class Solution {
private:
    vector<int> a;
    int n;
public:
    Solution(vector<int>& a) {
        this->a = a;
        this->n = a.size();
    }

    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return a;
    }

    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        auto b = a;        
        for (int i = 0; i < n; i++) {
            swap(b[i], b[i + rand() % (n - i)]);
        }
        return b;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(nums);
 * vector<int> param_1 = obj->reset();
 * vector<int> param_2 = obj->shuffle();
 */



#include <iostream>
using namespace std;

const int N = 10000;
int a[N], f[N];
int n;

// 状态表示:f[i] 表示所有以 a[i] 为结尾的上升子序列的最大长度
// 状态计算:f[i] = max(f[0], f[1], ... , f[i - 1], f[i])

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res = max(res, f[i]);
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

#include <iostream>

using namespace std;
const int N = 510;
int a[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }

    for (int j = n - 1; j >= 1; j--) {
        for (int i = n - 1; i >= j; i--) {
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
        }
    }

    cout << a[1][1] << endl;
    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

#include <iostream>

using namespace std;

const int N = 110;
int v[N][N], w[N][N], s[N], f[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++) cin >> v[i][j] >> w[i][j];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 0; j--) {
            for (int k = 1; k <= s[i]; k++) {
                if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
        }
    }
    cout << f[m] << endl;

    return 0;
}



解题思路

小学四年级追及问题

代码

class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *h) {
        if (!h || !h->next) return nullptr;
        auto p = h->next->next, q = h->next;
        while (p->next->next && p != q) p = p->next->next, q = q->next;
        if (!p->next->next) return nullptr;
        p = h;
        while (p != q) p = p->next, q = q->next;
        return p;
    }
};



解题思路

QQ20210507-124140.png

代码

原始做法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[N][K][2];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i++) f[i][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            f[i][j][0] = max(f[i - 1][j][1] + w[i], f[i - 1][j][0]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
    }

    int res = 0;
    for (int i = 0; i <= k; i++) {
        res = max(res, f[n][i][0]);
    }
    cout << res << endl;

    return 0;
}

滚动数组优化

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[K][2];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            f[j][0] = max(f[j][1] + w[i], f[j][0]);
            f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
        }
    }

    int res = 0;
    for (int i = 0; i <= k; i++) {
        res = max(res, f[i][0]);
    }
    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1049. 大盗阿福

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int w[N], f[N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> w[i];
        f[1] = w[1];
        for (int i = 2; i <= n; i++) {
            f[i] = max(f[i - 2] + w[i], f[i - 1]);
        }
        cout << f[n] << endl;;
    }
    return 0;
}


活动打卡代码 AcWing 1058. 股票买卖 V

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int w, f[3];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) ;

    f[0] = f[1] = -0x3f3f3f, f[2] = 0;
    for (int i = 1; i <= n; i++) {
            cin >> w;
            int a = max(f[0], f[2] - w);
            int b = f[0] + w;
            int c = max(f[1], f[2]);
            f[0] = a;
            f[1] = b;
            f[2] = c;
    }

    cout << max(f[1], f[2]) << endl;

    return 0;
}



解题思路

QQ20210507-133703.png

通过赋值无穷,标记非法状态。取最大值,所以标记负无穷

入口:可以买也可以不买,也就是手中无货且不在冷冻期的状态,也就是处于 2 状态

出口:因为是最大利润,所以手中肯定没货,也就是 1 2 状态

滚动变量优化空间:第 $i$ 层只依赖 $i - 1$ 层,所以从小到大迭代,计算到第 $i$ 层时 $i - 1$ 层已经计算过,所以可以用三个变量记录一下

代码

原始做法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int w[N], f[N][3];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];

    f[0][0] = f[0][1] = -0x3f3f3f, f[0][2] = 0;
    for (int i = 1; i <= n; i++) {
            f[i][0] = max(f[i - 1][0], f[i - 1][2] - w[i]);
            f[i][1] = f[i - 1][0] + w[i];
            f[i][2] = max(f[i - 1][1], f[i - 1][2]);
    }

    cout << max(f[n][1], f[n][2]) << endl;

    return 0;
}

滚动变量优化空间

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int w, f[3];

int main() {
    int n;
    cin >> n;

    f[0] = f[1] = -0x3f3f3f, f[2] = 0;
    for (int i = 1; i <= n; i++) {
            cin >> w;
            int a = max(f[0], f[2] - w);
            int b = f[0] + w;
            int c = max(f[1], f[2]);
            f[0] = a;
            f[1] = b;
            f[2] = c;
    }

    cout << max(f[1], f[2]) << endl;

    return 0;
}


活动打卡代码 AcWing 1057. 股票买卖 IV

解题思路

QQ20210507-124140.png

代码

原始做法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[N][K][2];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    for (int i = 0; i <= n; i++) f[i][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            f[i][j][0] = max(f[i - 1][j][1] + w[i], f[i - 1][j][0]);
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
        }
    }

    int res = 0;
    for (int i = 0; i <= k; i++) {
        res = max(res, f[n][i][0]);
    }
    cout << res << endl;

    return 0;
}

滚动数组优化

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, K = 110;
int w[N], f[K][2];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> w[i];

    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            f[j][0] = max(f[j][1] + w[i], f[j][0]);
            f[j][1] = max(f[j][1], f[j - 1][0] - w[i]);
        }
    }

    int res = 0;
    for (int i = 0; i <= k; i++) {
        res = max(res, f[i][0]);
    }
    cout << res << endl;

    return 0;
}