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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。