A Winged Steed

描述

有n种千里马，每一种都有若干匹，第i种马的颜值ai,价格di.现有m个牧马人要去挑选千里马，每一位牧马人对马的颜值都有要求：{所选马的颜值总和} ⩾Ai.现在让你来为牧马人做满足要求的最低预算.

输入

单组测试数据，第一行两个整数n,m,(1≤n,m≤1e4).

接下来nn行，每行两个整数a1,d1,a2,d2,...an,dn.

最后一行mm个整数A1,A2,...Am，(1≤ai,di,Ai≤1e4).

输出

输出m个整数占一行，用空格隔开，表示每一位牧马人的最低花费.

输入样例 1

2 21 22 15 5

输出样例 1

3 3

思路

完全背包，马的数量是无限的，把马看做是一个物品，把马的颜值看做物品的尺寸，牧马人对马的总颜值的要求看做是背包的体积，这样就转化成了一个完全背包问题。还有一点不同的是，要求满足>=总颜值要求的最小钱数。

比赛的时候卡到这里了，一直想不出来怎么处理相差的那部分，比赛后一看别人的代码，发现好简单，好神奇。就用了一个if就解决了问题。具体的解释放到代码里了

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define ll long long#define ms(a) memset(a,INF,sizeof(a))#define pi acos(-1.0)#define INF 0x3f3f3f3fconst double E=exp(1);const int maxn=1e4+10;using namespace std;int dp[maxn];// 颜值相当于物品的尺寸，每个人所需要的最小颜值是背包的体积int beauty[maxn],money[maxn];int p[maxn];int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>beauty[i]>>money[i]; int res=0; for(int i=1;i<=m;i++) { cin>>p[i]; res=max(res,p[i]); } // 初始化处理dp ms(dp); dp[0]=0; for(int i=1;i<=n;i++) { // j表示当前所需要的颜值 for(int j=1;j<=res;j++) { // 如果这个人对颜值的需求小于这匹马的需求，所花费的钱数变成dp[j]和money[i]中的较小者 // ！！！这个if是关键 if(j

转载于:https://www.cnblogs.com/Friends-A/p/10324398.html

你可能感兴趣的文章