B. Array Walk

zz/2024/5/21 21:41:15

传送门

分析

这题的题意大概就是有1-n个点,每个点赋值为a[i],现在可以移动k次,不过只能向左移动z次,并且不能连续向左移动,问你最后走过所有点的和最大是多少
这题很明显思路是一个dp,但是怎么进行状态转移是个问题,比赛的时候我想的是枚举每一个点,再枚举中间的点作为返回的点,后来发现代码并不好写

其实我们可以这样考虑,因为题目中说了,不会连续向左移动,也就是说我们每次向左移动一次,下一步就必然要向右移动,然后向左向右移动都可以,所以我们可以枚举当前到达的点,和已经向左组走过的次数即可,然后根据当前位置和向左走的次数可以计算总共移动的次数,然后判断是否需要记录答案

代码

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;
typedef long long ll;const int N = 1e5 + 10;
ll f[N][10];
int n,k,z;
ll a[N];int main(){int T;scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&k,&z);ll ans = 0;for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);for(int i = 1;i <= n;i++){f[i][0] = f[i - 1][0] + a[i];int s = a[i] + a[i - 1];if(i - 1 == k) ans = max(ans,f[i][0]);for(int j = 1;j <= z;j++)for(int q = 0;q <= j;q++){f[i][j] = max(f[i - 1][j - q] + q * s + a[i],f[i][j]);if(i - 1 + j * 2 == k) ans = max(ans,f[i][j]);if(i - 1 + j * 2 - 1 == k) ans = max(ans,f[i][j] - a[i]);}}for(int i=1;i<=n;i++)for(int j=0;j<=z;j++)f[i][j]=0;printf("%lld\n",ans);}
}

http://www.ngui.cc/zz/2727391.html

相关文章

Codeforces 954E:Water Taps 贪心

传送门 题目描述 ∀ x i ∈ [ 1 , a i ] , \forall x_i\in[1,a_i], ∀xi​∈[1,ai​],对于所有满足 ∑ i 1 n x i ( t i − T ) 0 \sum_{i1}^nx_i(t_i-T)0 ∑i1n​xi​(ti​−T)0的情况,求 ∑ i 1 n x i \sum_{i1}^nx_i ∑i1n​xi​的最大值 分析 我们可以计算大于m和小…

CodeForces 792C :Divide by Three DP + 路径还原

传送门 题目描述 在一个黑板上写着一个正整数 n 。它有不超过10^5位&#xff08;话说黑板上是怎么写下这个数的&#xff09; 。老师给你了一个任务&#xff0c;把它魔改成一个 美丽数 &#xff0c;而且因为你很懒&#xff0c;你非常非常的想用最小的步数把它改成一个 美丽数 …

CodeForces 372C :Watching Fireworks is Fun DP + 单调队列

传送门 题目描述 给出N个位子&#xff0c;排成一列&#xff0c;现在有M个烟花&#xff0c;每秒人的速度d&#xff0c;每个烟花有三个元素&#xff1a;a&#xff0c;b&#xff0c;t&#xff0c;表示在时刻t会绽放&#xff0c;如果我们在位子x观看到了的话&#xff0c;会获得b-…

CodeForces 961D:Pair Of Lines 思维

传送门 题目描述 在平面直角坐标系上给出n个点&#xff0c;求是否存在两条直线穿过所有点。 分析 前面三个点中&#xff0c;任意两个点必成一条直线&#xff0c;所以我们去枚举三个点中的两个&#xff0c;然后去判断其他的点是否在这条直线上&#xff0c;然后再判断不在这条…

CodeForces 319B :Psychos in a Line 单调栈

传送门 题目描述 有编号为1~N的N个人站成一排&#xff08;顺序是乱的&#xff09;&#xff0c;每人手中拿着一把枪。每一个时刻&#xff0c;每个人同时瞄准右边的人&#xff08;如果存在的话&#xff09;&#xff0c;然后如果这个人编号比自己大&#xff0c;则开枪将他打死。…

Wireless Password :ac自动机 + 状压DP

分析 f[i][j][k]表示第i位的情况下&#xff0c;在trie图上的位置位j的情况下匹配情况位k&#xff0c;状态转移方程就比较好写了 dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] (dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] dp[i][j][l]) % mod注意一下减去不合法的状态&#xff0c;节…

CodeForces 1367E :Necklace Assembly 思维

传送门 题目描述 给你一个字符串&#xff0c;你从中挑选一些让它们成为一个环&#xff0c;使得这个环朝一个方向转 k k k下&#xff0c;与原来看起来一样&#xff0c;找到你能够满足这个条件的可以挑选的最多的字符数量。 分析 我们去枚举 k k k的因子&#xff0c;那么我转…

POJ - 3635 :Full Tank? 最短路 + 拆点

分析 跟前段时间看的一个拆点求邻接矩阵快速幂的一个题有点像 这个题比较朴素的方法就是我把每个点剩余 j j j单位的汽油的最低花费处理出来&#xff0c;然后这样写毫无疑问会tle&#xff0c;所以我们需要去进行一些优化 首先我们思考一下这个朴素的思想为什么会超时&#xff…

CodeForces 546E :Soldier and Traveling 网络流 +拆点

传送门 题目描述 题意大概就是给定 n n n 个城市&#xff0c; m m m 条边。 然后人只能从走相邻边相连的城市。 现在给你初始城市的每一个人数&#xff0c;再给一组每个城市人数。询问是否可以从当前人数变换到给定人数。如果能&#xff0c;输入“YES”并输出方案&#xff0…

CodeForces 1312E : Array Shrinking 区间DP

传送门 题目描述 给你一个序列 a i a_{i} ai​&#xff0c;相邻两个数如果相同的话&#xff0c;我们可以删去其中一个数字&#xff0c;另一个数字1&#xff0c;最后留下来的序列最小可以是多少 分析 这个数据范围大概就能想到是区间DP问题了 我们首先初始化每一个区间f[i][…