住房与建设部网站,陕西城乡建设网,最新手机排行,网站的建设背景文章目录题目题解代码实现题目
小奇去遗迹探险#xff0c;遗迹里有N个宝箱#xff0c;有的装满了珠宝#xff0c;有的装着废品。 小奇有地图#xff0c;所以它知道每一个宝箱的价值#xff0c;但是它不喜欢走回头路#xff0c;所以要按顺序拿这N个宝箱中的若干个。
拿宝…
文章目录题目题解代码实现题目
小奇去遗迹探险遗迹里有N个宝箱有的装满了珠宝有的装着废品。 小奇有地图所以它知道每一个宝箱的价值但是它不喜欢走回头路所以要按顺序拿这N个宝箱中的若干个。
拿宝箱很累的。一开始小奇的体力是1 每得到一个宝箱之后小奇得到的价值是体力x 宝箱的价值之后它的体力就会变为原来的K倍 。
小奇不喜欢连续放过很多宝箱所以任意一段长度为M的序列中小奇一定要取走其中的一个宝箱。
现在小奇想知道它能得到的最大价值和。
输入格式 第一行两个整数 N,M表示的含义如题目中所述 第二行一个小数K 表示的含义如题目中所述最多4位小数 第三行,N个整数第i个整数表示第i个宝箱的价值。
输出格式 输出一行一个实数表示小奇能得到的最大价值和四舍五入保留两位小数。 题解
特别水也特别板的一道题。。。。 每个人都会想到三维DP DP[i][j][k]DP[i][j][k]DP[i][j][k]表示第i个宝箱一定选上一次选的宝箱为j选了k个 通过数据范围就已经扼杀了想开三维数组的心 那我就先舍弃k假设没有这个k的限制来思考一下 因为开二维都会MLE所以就死命也要把DP压成一维 DP[i]DP[i]DP[i]表示第i个宝箱一定选前面[1,i−1][1,i-1][1,i−1]不管怎么选反正要是合法的最大价值 转移方程式? DP[i]DP[j]w[i](j∈[i−m,i−1])DP[i]DP[j]w[i](j∈[i-m,i-1])DP[i]DP[j]w[i](j∈[i−m,i−1]) 这就是一个滑动窗口的优化单调队列我要AC了 但是因为有了k的限制我们就要重新搞一下了 我们思考如果正着往后推那么前面选了j个就会影响后面的价值 但是如果从后往前推后面管他选了x个对当前i的价值是没有影响的 当前i的价值只被前面的选取决定 所以重新定义一下DP[i]DP[i]DP[i] 表示从n往1推第i个宝箱必须选且[i1,j][i1,j][i1,j]的选取必须是合法的最大价值 转移方程式也就变了? DP[i]DP[j]w[i](j∈[i1,min(n1,im)])DP[i]DP[j]w[i](j∈[i1,min(n1,im)])DP[i]DP[j]w[i](j∈[i1,min(n1,im)]) 这里我只解释两个地方 1为什么要压一个n1 因为数据有可能在最后的[n,n−m1)[n,n-m1)[n,n−m1)全是负数 而这个时候i距离n的距离又不到m 我就可以不选这个时候就可以用DP[n1]0DP[n1]0DP[n1]0来处理
2为什么可以取到im 按我们的常规理解应该是[im−1,i][im-1,i][im−1,i] 仔细想想i是一定要取的那么[im−1,i][im-1,i][im−1,i]这个区间肯定是满足m的 但是[im,i−1][im,i-1][im,i−1]也是可以满足m的所以im也可能对i进行贡献
举例说明 m 2i 1i m 3 1 2 3 ↑ i [1,2]长度是m其中有下标为1的宝藏被拿了 [2,3]长度也是m所以下标为3的宝藏也应该被拿
代码实现
#include cstdio
#include deque
using namespace std;
#define MAXN 100005
deque int deq;
int n, m;
double k, result -0x7f7f7f7f;
double w[MAXN], dp[MAXN];int main() {scanf ( %d %d %lf, n, m, k );for ( int i 1;i n;i )scanf ( %lf, w[i] );deq.push_back ( n 1 );for ( int i n;i 1;i -- ) {while ( ! deq.empty() deq.front() i m )deq.pop_front();dp[i] dp[deq.front()] * k w[i];while ( ! deq.empty() dp[deq.back()] dp[i] )deq.pop_back();deq.push_back ( i );}for ( int i 1;i m;i )result max ( result, dp[i] );printf ( %.2lf, result );return 0;
}
