头像

BT7274

相信我!!!




离线:14分钟前


最近来访(522)
用户头像
flzj_kl
用户头像
张大迷糊爱唠叨
用户头像
蒟蒻小学生
用户头像
Misaka_9982
用户头像
裤头洗衣机
用户头像
听风_4
用户头像
求求了不要WA
用户头像
再也不会
用户头像
CV工程师_X
用户头像
handsomepyp
用户头像
benBiTouzi
用户头像
龚子昂
用户头像
MagicMooc
用户头像
夜色暮暮
用户头像
Tw_0
用户头像
蓬蒿人
用户头像
山海皆可平
用户头像
b11
用户头像
不care
用户头像
小熊饼干吃QQ

新鲜事 原文

BT7274
1小时前
自己一个人学很艰难啊。 心理压力特别大,没有别人的进度作为参考,自己一个人学容易懈怠,或者胡思乱想没有压力,进度也很乱啊。 先定一个小目标吧,把所有算法不相关的事情全部都戒掉。


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

BT7274
15小时前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n;
int f[N][3];
int w[N];

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

    memset (f, -0x3f, sizeof f);
    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][2], f[i - 1][1]);
    }

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

    return 0;
}


新鲜事 原文

BT7274
16小时前
做题快才是真的快!!!!!!!!! 谁看完视频不会敲代码啊??


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

BT7274
16小时前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = 110;

int f[N][M][2];
int n, m;
int w[N];

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

    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 <= m; j ++)
        {
            f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
            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 <= m; i ++) res = max(res, f[n][i][0]);

    cout << res << endl;

    return 0;
}


新鲜事 原文

BT7274
19小时前
y总提车了
图片



BT7274
23小时前

整理一下这一题的初始条件。

将所有的f都初始化为负无穷,只把第一遍历到的f点初始化为0。

我们先分析一下所有的dp问题的状态转移过程。首先i表示第i个物品,我们从第1个物品遍历到最后一个物品的过程中,所有的状态转移方程都是合法的,所有的状态转移得到的结果都是正确的,所以最起码我们要保证状态转移方程的初始值是正确的。

再来看i为0的情况,当i为0时f这个状态时没有任何意义的,也就是说无论状态划分是几维的,当i为0时f的状态都是没有任何意义的,所以在循环遍历的时候当这些i为0的状态向其他状态转移的时候一定不能影响其他状态的取值。因为其他有意义的状态按照正常的方式遍历下来就已经可以的得到正确答案了。

dp状态转移一共就这两部分了,两部分都保证正确了就能保证最后得到的状态转移是正确答案了。

回过头看一下我们从来不操心初始条件的背包问题。当第一个物品放进来的时候,无论j是多少,只要j符合转移条件,重量都等于0加上物品重量的本身。就算真的转移成了为0的状态,也意味当前没有物品放进来,所以值转移成0。对于一个背包来说,没有物品放进来,重量为零完全符合转移条件。
到这里我们可以看到背包问题特别特殊,初始状态转移方程为0是符合初始状态的转移条件的,甚至于当i为0的时候所有的状态转移方程都符合状态转移方程得出来的结果。所以我们做背包问题的时候完全不用管初始值,定义好初始f数组就好了。

我们再来看一下普通的dp问题怎么考虑。首先我们要先看i为0的状态转移成i为1的状态转移方程,先要保证这一部分的状态转移方程的结果要是正确的。
再分析题目的性质,如果题目中f值更新的时候有可能是递减的,那初始值全部定义成0的化就会覆盖本来这个状态的负值,导致最后影响结果。这时候就需要定义成一定不会影响状态转移的值,如求最大值的时候全部初始化为负无穷等等。

例如能量石那一道题,y总在视频里面写的时候没有加w与0取最大值的判断条件,那么他就需要把初始值全部搞成负无穷,当然那样是错的,因为根据题意吸收能量不能是负数。但是能保证状态转移中只根据有效的状态来转移,详情可以看墨染空的代码。

这一题也是这样,只能先买再卖,不能做空。那意味着持续下跌的情况下,状态机的转移过程中可能会出现亏损的负值。遇到这种情况,只要能分析出正确的状态转移方程,然后全部初始成负无穷按照正确的初始状态一步一步转移就一定是对的。

至于说分析什么可以直接买卖,保底不亏为0,然后分析每一个边界状态看一下有没有别的特判方法和边界处理方法。
我的评价是:《可以,但是没必要》



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

BT7274
1天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int w[N];
int f[N][2];

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

    while (T --)
    {
        int n;
        cin >> n;

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

        f[0][0] = 0, f[0][1] = -1e9;

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

        int res = max(f[n][0], f[n][1]);

        cout << res << endl;

    }

    return 0;
}


新鲜事 原文

BT7274
1天前
世上无难事,只要肯放弃,第三题不做了。 本来就不会,ai还爆int了,让我自己写高精度不如杀了我。 第一次打周赛,之前从来都没有打过比赛。 基础课只是过了一遍有个印象,还没有复习。 提高课第一章都没有看完。 哎。。。。。还是把课刷完,系统性的训练一下再打比赛吧。 感觉就是瞎搞。 第一题签到题都做了十几分钟。。。。。


新鲜事 原文

BT7274
1天前
闲来无事打个周赛吧。。。。


新鲜事 原文

BT7274
1天前
y总已经五天没有更新过b站视频了。 每天早上到十点钟acwing都没有上线。 不知道他在憋什么大招啊。。。