P1757 通天之分组背包 / hdu1712 ACboy needs your help (分组背包入门)
2024-10-17 06:29:15
hdu1712题意:A[i][j]表示用j天学习第i个课程能够得到A[i][j]的收益,求m天内获得的收益最大值,一天只能上一节课(转)。
分组背包套路:
for(int i=;i<=组数;++i)
for(int j=容量;j>=;--j)
for(int k=;k<=第i组元素个数;++k)
…………
保证一组只选<=1个
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int max(int &a,int &b){return a>b?a:b;}
int n,m,a[][],f[];
int main(){
while(~scanf("%d%d",&n,&m)){
if(!n&&!m) break;
for(re int i=;i<=n;++i)
for(re int j=;j<=m;++j)
scanf("%d",&a[i][j]);
memset(f,,sizeof(f));
for(re int i=;i<=n;++i)
for(re int j=m;j>=;--j)
for(re int k=;k<=j;++k)
f[j]=max(f[j],f[j-k]+a[i][k]);
printf("%d\n",f[m]);
}return ;
}
hdu1712 code
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int max(int &a,int &b){return a>b?a:b;}
int n,m,f[];
int len[],a[][],b[][];
int main(){
int q1,q2,q3,mc;
while(~scanf("%d%d",&m,&n)){
memset(len,,sizeof(len));
memset(f,,sizeof(f));
mc=;
for(re int i=;i<=n;++i){
scanf("%d%d%d",&q1,&q2,&q3);
mc=max(mc,q3);
a[q3][++len[q3]]=q1;
b[q3][len[q3]]=q2;
}
for(re int i=;i<=mc;++i)
for(re int j=m;j>=;--j)
for(re int u=;u<=len[i];++u)
if(j>=a[i][u])
f[j]=max(f[j],f[j-a[i][u]]+b[i][u]);
printf("%d\n",f[m]);
}return ;
}
P1757 code
最新文章
- Java Persistence with Hibernate
- Mockups Mockplus 网页原型设计
- if __name__ == &#39;__main__&#39;:
- ASP.NET页面间传值总结
- AJAX中UPDATEPANEL配合TIMER控件实现局部无刷新
- __LINE__ __DATE__ __FILE__ __TIME__ 等宏定义解释
- [AngularJS] Adding custom methods to angular.module
- Intellij Idea 创建EJB项目入门(一)
- Unity 扩展属性自定义绘制
- c#操作word文档之简历导出
- boost进程间通信经常使用开发一篇全(消息队列,共享内存,信号)
- Binder机制,从Java到C (1. IPC in Application Remote Service)
- ice调通过iceReplica用所有server instance的方法---客户端控制服务端的负载均衡
- Puzzles
- 手机自动化测试:appium源码分析之bootstrap七
- Stacked Regression的详细步骤和使用注意事项
- 统计学习方法学习(四)--KNN及kd树的java实现
- 手动编译安装nginx
- Java8的Stream语法详解(转载)
- nginx概述