思路：由于防御和血量的范围很小，所以暴力枚举出对于每种防御造成的每种伤害所需的最小花费，最后只需在伤害大于等于血量的情况下再找到最小花费（这个只需要后缀最小值预处理一下就可以了）

状态：dp[i][j]表示对防御为i的怪兽造成伤害为j的所需最小晶石花费。

状态转移方程：dp[i][j]=min(dp[i][j]，dp[i][j-t])(t表示每种技能造成的伤害，t=p-i，t>0)

代码1：

 

#include
     
      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+5;//必须开2e3,因为造成的伤害是大于等于血量的（1000+1000）const int M=1e5+5;int dp[11][N];int a[M],b[M],k[N],p[N];int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        for(int i=0;i
      
       =0;j--)            {                dp[i][j]=min(dp[i][j+1],dp[i][j]);//求一下后缀最小值            }        }        ll ans=0;        bool flag=false;        for(int i=0;i
      
     

 

 

 

 代码2：

上面那个代码是先枚举技能再枚举伤害的，这个代码是先枚举伤害再枚举技能的，相比而言这个要慢一些，因为上面那个枚举技能时就知道伤害的范围（下界即t）,相当于下面这个代码剪过枝了。

 

#include
     
      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+5;const int M=1e5+5;int dp[11][N];int a[M],b[M],k[N],p[N];int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        for(int i=0;i
      
       j)continue;                    dp[i][j]=min(dp[i][j-t]+k[l],dp[i][j]);                }            }            for(int j=N-2;j>=0;j--)            {                dp[i][j]=min(dp[i][j+1],dp[i][j]);            }        }        ll ans=0;        bool flag=false;        for(int i=0;i