【简单DP】CF867C George and Job

落日映苍穹つ 2024-03-22 17:08 50阅读 0赞

**写了几次MLE了**

**原因是没注意到最优情况一定是a\[N\]取右端点**

**所以不用多开3倍空间**

[Problem - C - Codeforces][]

题意：

![35b00911cfe5478888793de7670befd4.png][]

思路：

一开始的思路：

![666621da1d2b4b86af8206a9f2ca48ee.jpeg][]

实际上不用讨论作为左端点右端点

直接作为右端点即可

![680da40f9ed948b5b2dfb3cc853246da.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using i64 = long long;
    
    using namespace std;
    
    const int mxn=5e3+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    
    
    int N,M,K;
    int p[mxn];
    int s[mxn];
    int dp[mxn][mxn];
    
    void solve(){
    	cin>>N>>M>>K;
    	for(int i=1;i<=N;i++) cin>>p[i],s[i]=s[i-1]+p[i];
    	dp[1][1]=s[1];
    	for(int i=1;i<=N;i++){
    		for(int k=1;k<=K;k++){
    			dp[i][k]=dp[i-1][k];
    			if(i-M+1>=1){
    				dp[i][k]=max(dp[i-1][k],dp[i-M][k-1]+s[i]-s[i-M]);
    			}
    		}
    	}
    	cout<<dp[N][K]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/467/problem/C
[35b00911cfe5478888793de7670befd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0d03dae8136a4d68be0d2515edc69b09.png
[666621da1d2b4b86af8206a9f2ca48ee.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/669787d0f92f4875a038c07205b5c876.png
[680da40f9ed948b5b2dfb3cc853246da.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/4ca56292215e49c7b4839aa7b43b3817.png

发表评论取消回复

表情：

评论列表（有 0 条评论，50人围观）

还没有评论，来说两句吧...

相关阅读

相关【简单DP】CF867C George and Job

写了几次MLE了原因是没注意到最优情况一定是a\[N\]取右端点所以不用多开3倍空间 [Problem - C - Codeforces][] 题意： ![35b

落日映苍穹つ/ 2024年03月22日 17:08/ 0 赞/ 51 阅读

相关 C语言重构【867】转置矩阵

文章目录所有题目源代码：题目方案：复杂度计

旧城等待，/ 2023年01月05日 12:16/ 0 赞/ 172 阅读

相关 linux c server and client 简单的通信

server.c \include <stdlib.h> \include <stdio.h> \include <errno.h> \include <stri

客官°小女子只卖身不卖艺/ 2022年08月02日 05:42/ 0 赞/ 127 阅读

相关【3】More About Jobs and Job Details

参考链接[http://www.quartz-scheduler.org/documentation/quartz-2.2.x/tutorials/tutorial-lesso

秒速五厘米/ 2022年07月15日 23:50/ 0 赞/ 168 阅读

相关 CodeForces - 467A - A. George and Accommodation

-------------------- 题目连接：http://codeforces.com/problemset/problem/467/A 题目描述 Desc

た入场券/ 2022年06月12日 07:18/ 0 赞/ 177 阅读

相关 Elastic-Job之简单Job

简介 elastic-job是当当网开源的基于zookeeper和quartz实现的分布式作业调度框架。github地址是[https://github.com/dang

我就是我/ 2022年06月04日 06:29/ 0 赞/ 355 阅读

相关 LeetCode867. 转置矩阵

给定一个矩阵 `A`，返回 `A` 的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。示例 1：输入：[[1,2,3],[4,5,

迷南。/ 2022年05月17日 03:04/ 0 赞/ 194 阅读

相关 leetcode 867. 转置矩阵

给定一个矩阵 `A`，返回 `A` 的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。示例 1：输入：[[1,2,3],[4

墨蓝/ 2022年04月16日 05:34/ 0 赞/ 200 阅读

相关 LeetCode 867 转置矩阵

题目描述：给定一个矩阵 `A`，返回 `A` 的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。示例 1：输入：[[1,2,3

爱被打了一巴掌/ 2022年04月06日 12:52/ 0 赞/ 213 阅读

相关【Leetcode_easy】867. Transpose Matrix

problem [867. Transpose Matrix][867._Transpose Matrix] 参考 1. [Leetcode\_easy\_867

迈不过友情╰/ 2021年12月03日 04:19/ 0 赞/ 451 阅读