hdu 3732
#include<stdio.h>
#include<string.h>
int n,m,dp[10001];
int max(int a,int b) {
return a>b?a:b;
}
void yi(int val,int co) {
int i;
for(i=m;i>=co;i--)
dp[i]=max(dp[i],dp[i-co]+val);
}
void duo(int val,int co) {
int i;
for(i=co;i<=m;i++)
dp[i]=max(dp[i],dp[i-co]+val);
}
void seach(int val,int co,int num) {
if(co*num>m)
duo(val,co);
else {
int k=1;
while(k<num) {
yi(val*k,co*k);
num-=k;
k*=2;
}
yi(num*val,co*num);
}
}
int main() {
int p[11][11],i,j,k,t;
char s[101];
while(scanf("%d%d",&n,&m)!=EOF) {
memset(p,0,sizeof(p));
int a,b;
while(n--) {
scanf("%s%d%d",s,&a,&b);
p[a][b]++;
}
memset(dp,0,sizeof(dp));
for(i=0;i<=10;i++)
for(j=0;j<=10;j++)
if(p[i][j])
seach(i,j,p[i][j]);
printf("%d\n",dp[m]);
}
return 0;
}
另附详解地址:http://qianmacao.blog.163.com/blog/static/203397180201222591228542/
最新文章
- MyEclipse生成注册码
- Deep Learning 11_深度学习UFLDL教程:数据预处理(斯坦福大学深度学习教程)
- JavaScript进阶内容1:各种对象类型判断
- Android启停调试
- C++中关于const的思考
- Bloom Filter概念和原理
- VLC-Android和VLC几个关键宏定义的分析
- MongoDB使用手册
- 使用DateTimeOffset 对xml中的日期时间格式时区进行处理
- 学习string,stringBuffer时遇到的问题
- ubuntu 16.04 国内仓库地址
- Html 符号
- Scrapy-Splash的介绍、安装以及实例
- WPFの获取任意元素的位置
- dalaozouleyeyaojianqiangdehuoxiaqu
- Python 标准库一览(Python进阶学习)
- codeforces 578c//Weakness and Poorness// Codeforces Round #320 (Div. 1)
- Pywinauto 基于Win32 程序的自动化功能测试工具
- 如何将Excel导入到Mysql数据库中
- redis订阅与发布(把redis作为消息中间件)