Atcoder Beginner Contest145E(01背包记录路径)
#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[3007],b[3007];
int dp[3007],vis[3007],path[3007][3007];
int c[3007];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,t;
cin>>n>>t;
for(int i=1;i<=n;++i)
cin>>a[i]>>b[i];
int m=t-1;
for(int i=1;i<=n;++i){
for(int j=m;j>=a[i];--j){
if(dp[j]<dp[j-a[i]]+b[i]){
dp[j]=dp[j-a[i]]+b[i];
path[i][j]=1;
}
}
}
int tamp=m;
int cnt=0;
int ans=dp[m];
for(int i=n;i;--i){
if(path[i][tamp]){
vis[i]=1;
tamp-=a[i];
}
}
for(int i=1;i<=n;++i)
if(!vis[i])
c[++cnt]=b[i];
int mx=0;
for(int i=1;i<=cnt;++i)
mx=max(mx,c[i]);
ans+=mx;
cout<<ans;
return 0;
}
最新文章
- PHP之初识PHP(1)
- Servlet基础
- C# 中通过API实现的打印类
- Lua 常用的shell命令
- 剑指offer——替换字符串
- puppet运维配置实列
- 张高兴的 Windows 10 IoT 开发笔记:BMP180 气压传感器
- Nginx软件部署配置过程
- js中的语句
- 3.移植驱动到3.4内核-移植DM9000C驱动
- Docker常见仓库MongoDB
- .NET Core 微服务架构 Steeltoe 使用(基于 Spring Cloud)
- 4-2 requests库使用
- 一个ArrayList在循环过程中删除,会不会出问题,为什么?
- WCF中的ServiceHost初始化两种方式
- AI与RPA
- 《HTTP 权威指南》笔记:第十二章 基本认证体制
- mui plus.uploader.createUpload 上传文件服务端获取文件名中文乱码问题
- 爬虫浅谈一:一个简单c#爬虫程序
- hdu2061 Treasure the new start, freshmen!(暴力简单题)