首页 > 代码库 > hdu3602（变形背包）

hdu3602（变形背包）

2024-08-06 13:45:17   221人阅读

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3602

 

题意是：N个国家，M个飞船，每个国家有人数num，如果上飞船就给联合国value钱，选出某些国家上船且每个国家所有人都必须在同一艘船上，使联合国赚得的钱最多，而且被选出的国家上船的顺序必须和原给的国家顺序一致。

 

分析：dp[M][K]表示第M条船用了容量K的最大价值，O(NMK)的算法行不通

         变形：dp[i]表示获得价值i需要花费最少的代价（用了的船位）

 

#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010using namespace std;int t,n,m,k;int dp[N];int cal(int x,int y){    int num=ceil(x*1.0/k);    if(x+y<=num*k)return x+y;    //剩余量为k-y，因为前面的船无论还有多少船位，后面的人无法逆序上去了    else return num*k+y;}int main(){    scanf("%d",&t);    while(t--)    {        scanf("%d%d%d",&n,&m,&k);        memset(dp,0x3f,sizeof(dp));        dp[0]=0;        for(int i=1;i<=n;i++)        {            int a,b;            scanf("%d%d",&a,&b);a++;            for(int i=10000;i>=b;i--)            {                if(dp[i-b]!=inf)                dp[i]=min(dp[i],cal(dp[i-b],a));            }        }        int ans;        for(int i=10000;;i--)        {            if(dp[i]<=m*k)            {                ans=i;break;            }        }        printf("%d\n",ans);    }}
View Code

 

hdu3602（变形背包）


联系
我们