P2967 [USACO09DEC]视频游戏的麻烦Video Game Troubles
2024-08-30 22:02:21
冲刺阶段的首篇题解!
题目链接:P2967 [USACO09DEC]视频游戏的麻烦Video Game Troubles;
题目概述:
总共N个游戏平台,金额上限V元,给出每个游戏平台的价钱和其上游戏数量;
每个游戏有一个花费及愉悦值,求在花费不超上限的情况下,最大的愉悦值。
(1 <= N <= 50)
(1 <= V <= 100,000)
每个游戏平台价格(1 <= P_i <= 1000)
每个平台游戏数量(1 <= G_i <= 10)
每个游戏价格(1 <= GP_j price <= 100)
游戏带来的愉悦值 (1 <= PV_j <= 1,000,000)
解析:
最开始想到方程为dp[i][j]={dp[i-1][j-x],dp[i-1][j]};
表示第i个平台花j元的最大愉悦值。
由于每次dp[i][j]求解都只会和它前一层也就是dp[i-1]一层有关系,所以很明显,可以采用滚动数组优化。
但是数组是什么含义,需要斟酌一下,我选择去掉表示游戏平台的i,剩下dp[i]表示当前花费为i的最大愉悦值。
但是我们发现,对于第i个平台,要么不取,要么取(废话)。
而每个平台在求解的过程中会干扰前边求过的最优值。
所以就可以分出一个数组用于求当前平台一定取的最优值,而另一个就代表全局的最优值。
code:
#include<bits/stdc++.h>
using namespace std;
const int MAXV =1e6+;
int n,V,dp[MAXV];//表示价钱为i时的最高产奶量;
int dp2[MAXV];//表示第当前游戏平台一定取并价钱为i时的最高产奶量
int main()
{
cin>>n>>V;
for(int i=;i<=V;i++)dp[i]=;//表示价钱为i时的最高产奶量
for(int i=;i<=n;i++){//处理到第i个游戏平台
int temp,k;
cin>>temp>>k;
for(int c=temp;c<=V;c++)dp2[c]=dp[c-temp];//初始化成第i个平台当前只取了游戏主机的价钱
for(int j=;j<=k;j++){
int p,v;
cin>>p>>v;
for(int c=V-p;c>=temp;c--)
if(dp2[c+p]<dp2[c]+v)dp2[c+p]=dp2[c]+v;
}
for(int c=temp;c<=V;c++)
if(dp[c]<dp2[c])dp[c]=dp2[c];
}
cout<<dp[V];
return ;
}
加油!
最新文章
- iOS点击推送消息跳到应用指定页面
- Node.js与Sails~自定义响应体responses
- 分享50款 Android 移动应用程序图标【下篇】
- Facebook开源动画库 POP-小实例
- 用CSS3实现背景的固定
- document的一点点
- EXCEL 保存之前校验
- HTML5中DOM元素的querySelector/querySelectorAll的工作机制
- MySQL在windows和linux下的表名大小写问题
- linux常用命令之tail
- win32下用VC扩展PHP全过程
- 静态化 - 伪静态技术(Apache Rewrite 实现)
- 基于visual Studio2013解决C语言竞赛题之1082迷宫
- 发挥jQuery的威力
- PHP输出函数print, printf, sprintf的区别
- Python3.x和Python2.x的区别【转】
- Maven教程(1)--maven的下载、安装与配置
- GIL:全局解释器锁 VS 用户程序锁
- laravel C层接收数据的步骤
- onsaveInstanceState有关问题