HDOJ(HDU).4508 湫湫系列故事――减肥记I (DP 完全背包)

2019-11-08 01:50:39

字体：大中小

来源：转载

供稿：网友

HDOJ(HDU).4508 湫湫系列故事――减肥记I (DP 完全背包)

题意分析

裸完全背包

代码总览

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 100005#define nn 105using namespace std;int dp[nmax];struct item{ int hap; int kal; double rate;}a[nmax];bool cmp(item a,item b){ return a.rate>b.rate;}int main(){ //freopen("in.txt","r",stdin); int n; while(scanf("%d",&n) != EOF){ memset(dp,0,sizeof(dp)); for(int i = 1; i<=n; ++i) {scanf("%d%d",&a[i].hap,&a[i].kal); a[i].rate = a[i].hap/a[i].kal;} sort(a+1,a+1+n,cmp); int m; scanf("%d",&m); for(int i =1; i<=n; ++i){ for(int j =a[i].kal;j<=m;++j){ dp[j] = max(dp[j],dp[j-a[i].kal]+a[i].hap); } } PRintf("%d/n",dp[m]); } return 0;}

上一篇：第49篇一对多实现（六）学生进入只显示一个头像及删除学生id及删除学生div及 array_merge

下一篇：集合类型的并发