百度之星2017资格赛1003 度度熊与邪恶大魔王

本文主要是介绍百度之星2017资格赛1003 度度熊与邪恶大魔王，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

度度熊为了拯救可爱的公主，于是与邪恶大魔王战斗起来。

邪恶大魔王的麾下有n个怪兽，每个怪兽有a[i]的生命值，以及b[i]的防御力。

度度熊一共拥有m种攻击方式，第i种攻击方式，需要消耗k[i]的晶石，造成p[i]点伤害。

当然，如果度度熊使用第i个技能打在第j个怪兽上面的话，会使得第j个怪兽的生命值减少p[i]-b[j]，当然如果伤害小于防御，那么攻击就不会奏效。

如果怪兽的生命值降为0或以下，那么怪兽就会被消灭。

当然每个技能都可以使用无限次。

请问度度熊最少携带多少晶石，就可以消灭所有的怪兽。

Input

本题包含若干组测试数据。

第一行两个整数n，m,表示有n个怪兽，m种技能。

接下来n行，每行两个整数，a[i],b[i]，分别表示怪兽的生命值和防御力。

再接下来m行，每行两个整数k[i]和p[i]，分别表示技能的消耗晶石数目和技能的伤害值。

数据范围:

1<=n<=100000

1<=m<=1000

1<=a[i]<=1000

0<=b[i]<=10

0<=k[i]<=100000

0<=p[i]<=1000

Output

对于每组测试数据，输出最小的晶石消耗数量，如果不能击败所有的怪兽，输出-1

Sample Input

1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6

Sample Output

6
18

思路为dp，代码赛后公布。
祝大家有好成绩。

转载，访问量++，美滋滋。

#include <cmath>  
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
#include <iostream>  
#include <map>  
#include <algorithm>  
using namespace std;  #define pi acos(-1)  
#define endl '\n'  
#define srand() srand(time(0));  
#define me(x,y) memset(x,y,sizeof(x));  
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)  
#define close() ios::sync_with_stdio(0); cin.tie(0);  
#define FOR(x,n,i) for(int i=x;i<=n;i++)  
#define FOr(x,n,i) for(int i=x;i<n;i++)  
#define W while  
#define sgn(x) ((x) < 0 ? -1 : (x) > 0)  
#define bug printf("***********\n");  
typedef long long LL;  
const int INF=0x3f3f3f3f;  
const LL LINF=1e18+7;  
const int dx[]= {-1,0,1,0,1,-1,-1,1};  
const int dy[]= {0,1,0,-1,-1,1,-1,1};  
const int maxn=2005;  
const int maxx=1e5+100;  
const double EPS=1e-7;  
const int mod=998244353;  
template<class T>inline T min(T a,T b,T c)  
{  return min(min(a,b),c);  
}  
template<class T>inline T max(T a,T b,T c)  
{  return max(max(a,b),c);  
}  
template<class T>inline T min(T a,T b,T c,T d)  
{  return min(min(a,b),min(c,d));  
}  
template<class T>inline T max(T a,T b,T c,T d)  
{  return max(max(a,b),max(c,d));  
}  
inline LL Scan()  
{  LL Res=0,ch,Flag=0;  if((ch=getchar())=='-')Flag=1;  else if(ch>='0' && ch<='9')Res=ch-'0';  while((ch=getchar())>='0'&&ch<='9')Res=Res*10+ch-'0';  return Flag ? -Res : Res;  
}  LL dp[maxn][14];//dp[i][j]为花费 i为血 j为防   
LL a[maxx],b[maxx],k[maxn],p[maxn];  int main()  
{  //freopen( "in.txt" , "r" , stdin );  int n,m;  while(~scanf("%d%d",&n,&m))  {  for(int i=1;i<=n;i++)  {  a[i]=Scan();b[i]=Scan();  }  for(int i=1;i<=m;i++)  {  k[i]=Scan();p[i]=Scan();  }  for(int i=0;i<maxn;i++)  for(int j=0;j<=10;j++)  dp[i][j]=LINF;  for(int i=0;i<=10;i++)//防御   {  dp[0][i]=0;  for(int j=1;j<=m;j++)  {  LL t=p[j]-i;//破防的伤害  if(t<=0) continue;  for(int p=t;p<=2003;p++)  {  dp[p][i]=min(dp[p-t][i]+k[j],dp[p][i]);  }  }  for(int j=2002;j>=0;j--)//单调性   {  dp[j][i]=min(dp[j][i],dp[j+1][i]);  }  }  LL ans=0;  for(int i=1;i<=n;i++)  ans+=dp[a[i]][b[i]];  if(ans>=LINF)  puts("-1");  else cout<<ans<<endl;  }  
}