关键词:
题目描述
小明今天得到一个跳舞毯游戏程序Dance。游戏每次连续出N个移动的“箭头”,箭头依次标号为1到N,并且的相应的分数S[1..N]。如果你能“踏中”第i号箭头,你将获得相应的分数S[i];否则将被扣除相应的分数。
另外,游戏还有一个累计奖励机制:如果踏准次数累计达到T,并且是在踏中第i个箭头达到的,则将得到B[i]的奖励分数,累计也将清零,重新开始。
例如:N=6,T=3,相应的S和B分别为1,2,3,4,5,6、0,0,4,7,9,10,如果小明踏中所有箭头,则得分为:(1+2+3+4)+(4+5+6+10)=35
小明是个Dance高手,可以踏中他想踏中的任意一个箭头。但他发现,根据给定的N,T,S,B,踏中所有的箭头不一定能得最高分,小明很想知道最高能得多少分,你能帮助小明计算一下最多可得多少分吗?
输入输出格式
输入格式:第一行两个整数N和T。
第二行N个整数,为S的相应分数。
第三行也有N个整数,为B的相应分数。
输出格式:一个整数,可得到的最高分数。
输入输出样例
6 3
1 2 3 4 5 6
1 1 1 20 1 1
39
说明
【样例解释】
跳过第一个,扣1分,连踩3个,得9分,并获得附加分20分,之后再连踩2个,共39分。
【数据范围】
对于20%的数据0≤N,T≤100;
对于100%的数据0≤N,T≤5000;
S和B各有N个数,所有分数为[0,10000]之间的整数。
Solution:
本题不难。。。
第一眼一味可以随便走,那扣分的条件不就多余了吗?后面发现是从$1$开始依次到$n$,那么就是个线性的,直接二维枚举就好了。
设$f[i][j]$表示第$j$次在第$i$个位置时的最大值,初始化时$f[i][0]=f[i-1][0]-a[i]$(表示在不动到了第$i$个位置时的值从上一个位置转移过来,且要扣分),然后状态转移方程就显而易见了:
$f[i][j]=max(f[i-1][j-1]+a[i],f[i-1][j]-a[i])$,当$j\;mod\;m==0$时,转移时就是$f[i][j]=max(f[i-1][j]+a[i],f[i-1][j-1]+a[i]+b[i])$。
最后答案就是所有状态中的最大值拉。
代码:
1 // luogu-judger-enable-o2 2 #include<bits/stdc++.h> 3 #define il inline 4 #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) 5 #define Max(a,b) ((a)>(b)?(a):(b)) 6 #define Min(a,b) ((a)>(b)?(b):(a)) 7 using namespace std; 8 const int N=5005; 9 int n,m,a[N],b[N],f[N][N],ans=-233333333; 10 11 il int gi() 12 int a=0;char x=getchar(); 13 while(x<‘0‘||x>‘9‘)x=getchar(); 14 while(x>=‘0‘&&x<=‘9‘)a=(a<<3)+(a<<1)+x-48,x=getchar(); 15 return a; 16 17 18 int main() 19 n=gi(),m=gi(); 20 For(i,1,n)a[i]=gi(),f[i][0]=f[i-1][0]-a[i]; 21 For(i,1,n)b[i]=gi(); 22 For(i,1,n) 23 For(j,1,i) 24 f[i][j]=Max(f[i-1][j-1]+a[i],f[i-1][j]-a[i]); 25 if(j%m==0)f[i][j]=Max(f[i-1][j]-a[i],f[i-1][j-1]+b[i]+a[i]); 26 ans=Max(ans,f[i][j]); 27 28 29 cout<<ans; 30 return 0; 31
cqoi2009跳舞(代码片段)
...量彼此会出现不相等的情况。所以我们现在需要确定一下跳舞 查看详情
p3153[cqoi2009]跳舞(代码片段)
...向喜欢“)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?输入输出格式输入格式:第一行包 查看详情
[bzoj1305][cqoi2009]跳舞(网络流)(代码片段)
1305:[CQOI2009]dance跳舞TimeLimit:5Sec MemoryLimit:162MBSubmit:3944 Solved:1692[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳... 查看详情
如何用matlab为小姐姐跳舞视频增添另一个小姐姐跳舞进度条(代码片段)
注:本人非常清楚这项任务使用pr会简单很多,此篇文章只是为了探究matlab能干啥的边界。并作为一个熟悉matlab矩阵操作和视频音频操作的例子。效果如下:(怕侵权就只放个动图)可以看到小姐姐的舞蹈非常... 查看详情
如何用matlab为小姐姐跳舞视频增添另一个小姐姐跳舞进度条(代码片段)
注:本人非常清楚这项任务使用pr会简单很多,此篇文章只是为了探究matlab能干啥的边界。并作为一个熟悉matlab矩阵操作和视频音频操作的例子。效果如下:(怕侵权就只放个动图)可以看到小姐姐的舞蹈非常... 查看详情
1305:[cqoi2009]dance跳舞(代码片段)
TimeLimit: 5Sec MemoryLimit: 162MBSubmit: 4169 Solved: 1804[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两... 查看详情
制作一个小黄鸭转圈跳舞的页面。(代码片段)
我们来制作一个小黄鸭转圈跳舞的页面。分析一下1、分析一下这个页面,要完成这些效果,一共需要3步:把鸭子都放到一个盒子当中在盒子里,把每个鸭子的位置摆好让盒子旋转2、让鸭子在盒子中的位置摆好,需要怎么做:先... 查看详情
多任务-线程(代码片段)
...的,比如开车的时候手和脚共同来驾驶汽车,再比如唱歌跳舞也是同时进行的;试想,如果把唱歌和跳舞这2件事情分开依次完成的话,估计就没有那么好的效果了(想一下场景:先唱歌,然后在跳舞,O(∩_∩)O哈哈~)程序中如... 查看详情
bzoj1305:[cqoi2009]dance跳舞(二分答案+网络流)(代码片段)
1305:[CQOI2009]dance跳舞题目:传送门 题解: 一眼网络流基础建模...然后就GG了 二分答案+拆点建边+最大流判断: 把男女生拆为男1,男2,女1,女2 1、男1和男2还有女1和女2之间连边,流量为约束条件k 2、st连... 查看详情
码神军训(四,五)——代码跳舞军体拳(代码片段)
吹水今天,码神依旧凉爽,军体拳,摸鱼一天,所以早上就在操场趴着,**不过,我学会了,**信不信?看到抖音小姐姐的舞蹈,用代码做出来,还挺好看,我也想试一下,不会,... 查看详情
全网最火-跳舞的鸭子动态源码-超简单(代码片段)
全网最火-跳舞的鸭子动态源码-超简单效果图:<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title><style>@keyframesxuanzhuan0%transform:rotateX(-20deg)rotateY(0deg)100%transform:rotateX(-20deg)rotateY(360deg)bodybackgrou... 查看详情
字符串跳舞,保姆级教程,利用python实现小姐姐跳代码舞(代码片段)
代码舞源代码:video_2_code_video.py私信小编01即可获取大量python学习资源,最后,如果你的时间不是很紧张,并且又想快速的提高,最重要的是不怕吃苦,建议你可以联系维:762459510,那个真的很不错... 查看详情
[cqoi2009]跳舞(代码片段)
...看就是网络流了之后想一想怎么搞发现题目的意思是使得跳舞最少的男生跳的舞最多很自然想到二分答案啊现在转化成了一个判定性问题,能否使得所有人都跳上(k)只舞由于喜欢和不喜欢的人放在一起并不好限制,于是只能拆点... 查看详情
七夕限定不会编程也能送给她一个让字符串跳舞的视频(代码片段)
文章目录制作流程将视频转换成图片将图片转换成字符形式的图片提取音频图片合成视频并加音频总结七夕节到了,今天就来点不一样的内容吧!如何让你喜欢的视频变成字符串的形式扭动着!接下来我们先欣赏一下... 查看详情
关于哲哲跳舞这件小事儿(代码片段)
...的成长和每一位亲人都密切相关,今天我想谈谈关于哲哲跳舞这件小事儿。初心我们常常说一句话,叫做不忘初心,方得始终。做一件事情不要忘记了最初的目的是什么,既然叫做舞蹈兴趣学习班,那么重点就在“兴趣”和“学... 查看详情
$luogup2029$跳舞题解(代码片段)
一道不是十分水的(dp).首先我们考虑(dp)方程的构造。起初我定义的状态是(dp_i,j)表示前(i)个格子,总共跳了(j)次的最大得分。但事实上它并不可以转移,因为我们不知道新的一轮操作从之间的哪个格子算起。那么状态转移方程就... 查看详情
舞蹈课(dancinglessons)(代码片段)
...相邻的异性时,舞蹈技术相差最小的那一对会出列并开始跳舞。如果相差最小的不止一对,那么最左边的那一对出列。一对异性出列之后,队伍中的空白按原顺序补上(即:若队伍为ABCD,那么BC出列之后队伍变为AD)。舞蹈技术... 查看详情
bzoj1305:[cqoi2009]dance跳舞
题目链接bzoj1305:[CQOI2009]dance跳舞题解男,女生拆点A1A2,B1B2,拆成两点间分别连容量为K的边,限制与不喜欢的人跳舞的数量A1连接源点容量为x,B1连接汇点容量为x,x即为歌曲数目对与相互喜欢的男女直在A1,B1间接连容量为1的边... 查看详情