做题感悟:在比赛遇到这题本来是应该高兴的,但是做这题时剩下半个小时左右,时间是很充足(当时想到用多重背包解决),当时就不淡定了调试了好久也没调出来(写给不淡定的自己)。
解题思路:1)多重背包 这题一看就知道必须从后往前找(后面的不会对前面的造成影响),so 想到处理成多重背包,切记体积为重量。
2 ) 贪心 ( 很经典) 把每一点的单位重量从当前点到终点的总价值算出来(即:当前点的单位重量价值),那么只要排一下序单位价值从小到达依次贪心就可以。
代码(多重背包):
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define lld __int64 const double PI = 3.1415926 ; const double esp = 1e-4 ; const int md= 2810778 ; const int INF = 99999999 ; const int MX = 100005 ; int k,r,m,n,sum ; int w[MX],v[MX],dp[MX] ; // v[ ] 存体积 w[ ] 花费的价值 struct node { int x,v,w ; }T[MX] ; bool cmp(node a,node b) { return a.x > b.x ; } void search(int dis,int num,int wx) { for(int i=1 ;i<=num ;i=i<<1) { w[r++]=dis*i+i*wx ; v[r-1]=i ; num-=i ; } if(num) { w[r++]=dis*num+num*wx ; v[r-1]=num ; } } void init() { for(int i=1 ;i<=sum ;i++) dp[i]=INF ; dp[0]=0 ; } int main() { int Tx ; scanf("%d",&Tx) ; while(Tx--) { scanf("%d%d%d",&k,&m,&n) ; for(int i=0 ;i<n ;i++) scanf("%d%d%d",&T[i].x,&T[i].v,&T[i].w) ; sort(T,T+n,cmp) ; sum=0 ; r=0 ; int y ; for(int i=0 ;i<n ;i++) // 多重背包二进制优化 { y=m-T[i].x ; sum+=T[i].v ; search(y,T[i].v,T[i].w) ; } init() ; // 初始化 for(int i=0 ;i<r ;i++) for(int j=sum ;j>=v[i] ;j--) if(dp[j]>dp[j-v[i]]+w[i]) dp[j]=dp[j-v[i]]+w[i] ; int min=INF ; for(int i=k ;i<=sum ;i++) // 寻找最优解 if(min>dp[i]) min=dp[i] ; printf("%d\n",min) ; } return 0 ; }
代码(贪心):
#include<stdio.h> #include<iostream> #include<map> #include<stack> #include<string> #include<string.h> #include<stdlib.h> #include<math.h> #include<vector> #include<queue> #include<algorithm> using namespace std ; #define lld __int64 const double PI = 3.1415926 ; const double esp = 1e-4 ; const int md= 2810778 ; const int INF = 99999999 ; const int MX = 100005 ; int k,r,m,n,sum ; struct node { int v,w ; }T[MX] ; bool cmp(node a,node b) // 按价值小排序 { return a.w < b.w ; } int main() { int Tx ; scanf("%d",&Tx) ; while(Tx--) { scanf("%d%d%d",&k,&m,&n) ; int x,y ; for(int i=0 ;i<n ;i++) { scanf("%d%d%d",&x,&T[i].v,&y) ; T[i].w = m-x + y ; // 处理单价 } sort(T,T+n,cmp) ; int best=0 ; for(int i=0 ;i<n ;i++) // 从单价小的开始贪心 { if(T[i].v>=k) { best+=k*T[i].w ; break ; } else { k-=T[i].v ; best+=T[i].v*T[i].w ; } } printf("%d\n",best) ; } return 0 ; }