思路：由于防御和血量的范围很小，所以暴力枚举出对于每种防御造成的每种伤害所需的最小花费，最后只需在伤害大于等于血量的情况下再找到最小花费（这个只需要后缀最小值预处理一下就可以了）
状态：dp[i][j]表示对防御为i的怪兽造成伤害为j的所需最小晶石花费。
状态转移方程：dp[i][j]=min(dp[i][j]，dp[i][j-t])(t表示每种技能造成的伤害，t=p-i，t>0)
代码1：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
#define mem(a,b) memset((a),(b),sizeof(a))
const int INF=0x3f3f3f3f;
const int N=2e3+;//必须开2e3,因为造成的伤害是大于等于血量的（1000+1000）
const int M=1e5+;
int dp[][N];
int a[M],b[M],k[N],p[N];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for(int i=;i<m;i++)
{
scanf("%d%d",&k[i],&p[i]);
}
mem(dp,INF);
for(int i=;i<=;i++)
{
dp[i][]=;//所有状态的初始状态都是dp[i][0]
for(int j=;j<m;j++)
{
int t=p[j]-i;
if(t<=)continue;
for(int l=t;l<N;l++)
{
dp[i][l]=min(dp[i][l-t]+k[j],dp[i][l]);
}
}
for(int j=N-;j>=;j--)
{
dp[i][j]=min(dp[i][j+],dp[i][j]);//求一下后缀最小值
}
}
ll ans=;
bool flag=false;
for(int i=;i<n;i++)
{
ans+=dp[b[i]][a[i]];
if(dp[b[i]][a[i]]==INF)flag=true;//等于INF表示不存在这样的最小花费
}
if(flag)cout<<-<<endl;
else cout<<ans<<endl;
}
return ;
}
代码2：
上面那个代码是先枚举技能再枚举伤害的，这个代码是先枚举伤害再枚举技能的，相比而言这个要慢一些，因为上面那个枚举技能时就知道伤害的范围（下界即t）,相当于下面这个代码剪过枝了。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls rt<<1,l,m
#define rs rt<<1|1,m+1,r
#define pb push_back
#define mem(a,b) memset((a),(b),sizeof(a))
const int INF=0x3f3f3f3f;
const int N=2e3+;
const int M=1e5+;
int dp[][N];
int a[M],b[M],k[N],p[N];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for(int i=;i<m;i++)
{
scanf("%d%d",&k[i],&p[i]);
}
mem(dp,INF);
for(int i=;i<=;i++)
{
dp[i][]=;
for(int j=;j<N;j++)
{
for(int l=;l<m;l++)
{
int t=p[l]-i;
if(t<=||t>j)continue;
dp[i][j]=min(dp[i][j-t]+k[l],dp[i][j]);
}
}
for(int j=N-;j>=;j--)
{
dp[i][j]=min(dp[i][j+],dp[i][j]);
}
}
ll ans=;
bool flag=false;
for(int i=;i<n;i++)
{
ans+=dp[b[i]][a[i]];
if(dp[b[i]][a[i]]==INF)flag=true;
}
if(flag)cout<<-<<endl;
else cout<<ans<<endl;
}
return ;
}