【BZOJ4247】挂饰(动态规划)
规划 动态
2023-09-11 14:14:41 时间
【BZOJ4247】挂饰(动态规划)
题面
题解
设\(f[i][j]\)表示前\(i\)个物品中还剩下\(j\)个挂钩时的最大答案。
转移显然是一个\(01\)背包,要么不选:\(f[i][j]\rightarrow f[i-1][j]\)
要么选,那么首先这个物品至少要占用一个挂钩,然后它会贡献\(a[i]\)个挂钩,事实上如果\(a[i]\)之和太大那么和\(n\)没有区别,所以\(f[i][j]\rightarrow f[i-1][max(j-a[i],0)+1]+b[i]\)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
#define MAX 2020
inline int read()
{
int x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
int n;
struct Node{int a,b;}p[MAX];
bool operator<(Node a,Node b){return a.a>b.a;}
int f[MAX][MAX];
int main()
{
n=read();
for(int i=1;i<=n;++i)p[i].a=read(),p[i].b=read();
sort(&p[1],&p[n+1]);
memset(f,-63,sizeof(f));f[0][1]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<=n;++j)
f[i][j]=max(f[i-1][j],f[i-1][max(j-p[i].a,0)+1]+p[i].b);
int ans=-2147483647;
for(int i=0;i<=n;++i)ans=max(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}
相关文章
- 【华为云社区】悟一下动态规划
- Java实现 LeetCode 887 鸡蛋掉落(动态规划,谷歌面试题,蓝桥杯真题)
- Java实现 LeetCode 887 鸡蛋掉落(动态规划,谷歌面试题,蓝桥杯真题)
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- 搭建一个小型网络-规划、设计、配置
- 良好地去规划自己的学习
- 【 MAKEFILE 编程基础之二】MAKEFILE 书写规划以及语法规则!
- 背包问题(动态规划)
- LeetCode-396. 旋转函数【动态规划,思路清晰,错位相减法,迭代】
- Atitit 知识管理 知识的存储与检索 目录 1. Mis4大信息系统2 1.1. crm客户流 通讯录2 1.2. 企业资源规划(ERP) 财务卡片系统 通讯录,canlenda实现2
- 数学建模学习(16):动态规划模型之求两个单一节点之间的最短路径,超级详细!
- Objective-C路成魔【2-Objective-C 规划】
- 180:vue+openlayers 模仿共享单车,判断点是否放在规划的电子围栏内
- 开发人员这样规划自己的职业道路 初衷不变,方向万变,发展为大
- leetcode算法之动态规划总结(11种DP类型,70道全部搞懂)——总结非常全面
- 一维动态规划——字符串,可以使用dfs+cache,也可以改写为dp数组
- DFS和动态规划——字符串匹配 真蛋疼 为*的情况需考虑匹配0个、1个、2个情况 DFS会超时 正则匹配的话 需要向前看x*的情况 打包处理
- 07-图6 旅游规划
- 一文搞懂动态规划,上机考试再也不会慌
- 一文解析动态规划中的背包问题
- 动态规划04~什么?不会吧?做算法题可以帮你炒股?真的不可思议