HDU 3602 2012【01 背包变形】

题意: 有 n 个团队和 m 艘船，每艘船的载客量为 k，每个团队的人数为ai+1 ，转载该团队可获利润 bi,要求每个团队的所有人必须在同一艘船上，

且团队优先级高的团队所在船编号不能大于优先级低的团队，求可以获得的最大利润。

题解：其实没什么，只需要01背包就可以了，只不过优先考虑团队优先级高的。
分析：dp[i] 表示获得 i 利润时需要的最少船位，且要保证优先级高的团队优先考虑。

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #define INF 0x1f1f1f1f

 #define v 10005

 int min(int a,int b)

 {

     return a<b?a:b;

 }

 int dp[v+];

 int n,m,k;

 int cal(int num,int a)

 {

     int tot=(num+k-)/k;

     if(num+a<=tot*k)

         return num+a;

     return tot*k+a;

 }

 int main()

 {

     int Cas;

     scanf("%d",&Cas);

     while(Cas--)

     {

         scanf("%d%d%d",&n,&m,&k);

         memset(dp,INF,sizeof(dp));

         int a,b;

         dp[]=;

         while(n--)

         {

             scanf("%d %d",&a, &b);

             a++;

             for(int i=v-; i>=b; i--)

                 if(dp[i-b]!=INF)

                     dp[i]=min(dp[i],cal(dp[i-b],a));

         }

         int i;

         for(i=v; i>=; i--)

             if(dp[i]<m*k) break;

         printf("%d\n",i);

     }

 }

巴特西

HDU 3602 2012【01 背包变形】

最新文章

热门文章