首页 > 代码库 > poj 2392 (Space Elevator) 1276 (Cash Machine)变形背包
poj 2392 (Space Elevator) 1276 (Cash Machine)变形背包
这道题跟coins很像,看来楼教主的男人八题果然不简单。
进行coins式的背包处理就好了。
2392
#include<iostream> #include<algorithm> #include<string.h> #include<stdlib.h> #include<stdio.h> #define max(a,b) ((a)>(b)?(a):(b)) typedef long long ll; using namespace std; const int maxn=41000; struct P { int a,b,c; }p[maxn]; bool cmp( const struct P &a,const struct P&b) { return a.b<b.b; } int dp[maxn],use[maxn]; int n,m,T; int K; int main() { while(~scanf("%d",&K)) { int maxh=0; for(int i=1;i<=K;i++) scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c); sort(p+1,p+1+K,cmp); memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<=K;i++) { memset(use,0,sizeof(use)); for(int j=p[i].a;j<=p[i].b;j++) { if( dp[j-p[i].a]!=-1 && use[j-p[i].a]<p[i].c && dp[j-p[i].a]+p[i].a>dp[j] ) { use[j]=use[j-p[i].a]+1; dp[j]=dp[j-p[i].a]+p[i].a; maxh=max(maxh,dp[j]); } } } cout<<maxh<<endl; } return 0; }
1276
#include<iostream> #include<algorithm> #include<string.h> #include<stdlib.h> #include<stdio.h> #define max(a,b) ((a)>(b)?(a):(b)) typedef long long ll; using namespace std; const int maxn=10+1000; struct P { int a,c; }p[maxn]; int dp[maxn*1000],use[maxn*1000]; int n,m,T; int K; int main() { while(~scanf("%d",&K)) { int maxh=0; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].c,&p[i].a); memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;i++) { memset(use,0,sizeof(use)); for(int j=p[i].a;j<=K;j++) { if( dp[j-p[i].a]!=-1 && use[j-p[i].a]<p[i].c && dp[j-p[i].a]+p[i].a>dp[j] ) { use[j]=use[j-p[i].a]+1; dp[j]=dp[j-p[i].a]+p[i].a; maxh=max(maxh,dp[j]); } } } cout<<maxh<<endl; } return 0; }
poj 2392 (Space Elevator) 1276 (Cash Machine)变形背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。