AcWing 332. 股票交易

2021-03-17 23:25

阅读：667

标签：sizeof memset cstring 计划 print 表示 wing mat ref

大型补档计划

题目链接

\(f[i][j]\) 表示前 \(i\) 天，手里有 \(j\) 个股票挣得最多钱

买股票。枚举 \(u

\(f[i][j] = max(f[u][k] - (j - k) * AP[i]) = max(f[u][k] + k * AP[i]) - j * AP[i]\)

满足 \(j - AS[i]

设 \(pre[k]\) 为 \(f[1 ~ i - W][k]\) 的前缀 \(Max\) 维护即可。

剩下的用单调队列。

维护 \(pre[k] - k * AP[i]\) 递减的序列即可。

卖股票\(P\)，枚举 \(u

\(f[i][j] = f[u][k] + (k - j) * BP[i] = max(f[u][k] + k * BP[i]) - j * BP[i]\)

维护 \(pre[k] + k * AP[i]\) 递减的序列即可。

#include 
#include 
#include 
using namespace std;
const int N = 2005; 
int T, maxP, W, AP[N], BP[N], AS[N], BS[N];
int f[N][N], pre[N], q[N];

int main() {
    int ans = 0;
    memset(f, 0xcf, sizeof f);
    memset(pre, 0xcf, sizeof pre);
    pre[0] = 0;
    scanf("%d%d%d", &T, &maxP, &W);
    for (int i = 1; i  BS[i] + j) hh++;
            if (hh = 1) pre[j] = max(pre[j], f[i - W][j]);
            ans = max(ans, f[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

AcWing 332. 股票交易

标签：sizeof memset cstring 计划 print 表示 wing mat ref

原文地址：https://www.cnblogs.com/dmoransky/p/12380563.html

上一篇：windows安装sourceTree

下一篇：如何在Mac和Windows PC之间无线共享文件

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 332. 股票交易
文章链接：http://soscw.com/index.php/essay/65519.html

亲，登录后才可以留言！

AcWing 332. 股票交易

评论

热门文章

推荐文章

最新文章

置顶文章