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 2 1 2 2 1 5 5
输出样例 1
3 3
思路
完全背包，马的数量是无限的，把马看做是一个物品，把马的颜值看做物品的尺寸，牧马人对马的总颜值的要求看做是背包的体积，这样就转化成了一个完全背包问题。还有一点不同的是，要求满足>=总颜值要求的最小钱数。
比赛的时候卡到这里了，一直想不出来怎么处理相差的那部分，比赛后一看别人的代码，发现好简单，好神奇。就用了一个if就解决了问题。具体的解释放到代码里了
AC代码
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#define ll long long
#define ms(a) memset(a,INF,sizeof(a))
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
const 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<beauty[i])
dp[j]=min(dp[j],money[i]);
// 下面这里就是个完全背包了
else
dp[j]=min(dp[j],dp[j-beauty[i]]+money[i]);
}
}
// 按顺序输出所需的最小花费
for(int i=1;i<=m;i++)
{
if(i!=1)
cout<<" ";
cout<<dp[p[i]];
}
cout<<endl;
return 0;
}