A Winged Steed(背包)

描述

有n種千裡馬，每一種都有若幹匹，第ii種馬的顔值ai​,價格di​.現有m個牧馬人要去挑選千裡馬，每一位牧馬人對馬的顔值都有要求：{所選馬的顔值總和}⩾Ai​.現在讓你來為牧馬人做滿足要求的最低預算.

輸入

單組測試資料，第一行兩個整數n,m(1≤n,m≤1e4).

接下來n行，每行兩個整數a1​,d1​,a2​,d2​,...an​,dn​.

最後一行m個整數A1​,A2​,...Am​(1≤ai​,di​,Ai​≤1e4).

輸出

輸出m個整數占一行，用空格隔開，表示每一位牧馬人的最低花費.

輸入樣例 1 

2 2
1 2
2 1
5 5      

輸出樣例 1

3 3      

#include<iostream>
#include<cstring>
using namespace std;
int a[150000];
int d[150000];
int peo[150000];
int dp[150000]; 
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i]>>d[i];
	}
	int mmax=-1;
	for(int i=0;i<m;i++){ 
       cin>>peo[i];
	   mmax=max(mmax,peo[i]); 
	}
	memset(dp,0x3f3f3f3f,sizeof(dp));
	dp[0]=0;
	for(int i=0;i<n;i++){
		for(int j=1;j<=mmax;j++){
			   if(j>a[i]) 
			   dp[j]=min(dp[j],dp[j-a[i]]+d[i]);
		       else 
		       dp[j]=min(d[i],dp[j]);
		}
	}
	for(int i=0;i<m;i++){
		if(i!=m-1){
			cout<<dp[peo[i]]<<" ";
		}
		else 
		cout<<dp[peo[i]]<<endl;
	}
	return 0;
}