#代碼：

#include<bits/stdc++.h> #define MAXN 1050using namespace std; int n,m; long long int dp[MAXN][11]={0};//把防御值為j的怪物，生命值打掉i需要消耗的最少的水晶數(shù)。 long long int num[MAXN][11]={0};//num[i][j]生命值為i，防御為j的怪物個(gè)數(shù) int spend[MAXN],hit[MAXN]; long long int ans=0; int best[MAXN]; struct SKILL {int hit;int spend; }a[MAXN]; /*bool my_cmp(SKILL x,SKILL y) {if(x.spend!=y.spend)return x.spend>y.spend; }*/int main() {while(scanf("%d%d",&n,&m)!=EOF){ans=0;memset(num,0,sizeof(num));memset(dp,0,sizeof(dp));memset(best,0,sizeof(best));int max_hit=0,max_def=0,max_hp=0;int lx,ly;for(int i=0;i<n;i++){scanf("%d%d",&lx,&ly);num[lx][ly]++;if(max_def<ly)max_def=ly;if(max_hp<lx)max_hp=lx;}int l_num=0;for(int i=0;i<m;i++){scanf("%d%d",&lx,&ly);if(best[ly]!=0&&best[ly]<=lx)continue;best[ly]=lx;a[l_num].spend=lx;a[l_num].hit=ly;if(a[l_num].hit>max_hit){max_hit=a[l_num].hit;}l_num++;}m=l_num;if(max_hit<=max_def){printf("-1\n");continue;}//sort(a,a+m,my_cmp);for(int k_def=0;k_def<=10;k_def++)//枚舉所有防御力可能{//int min_cost=1000000,min_cost_num=-1;if(k_def!=0)for(int i=0;i<m;i++){a[i].hit--;}/*for(int i=0;i<m;i++)//找到最小花費(fèi){if(a[i].hit<=0)continue;if(a[i].cost<=min_cost){min_cost=a[i].cost;min_cost_num=i;}}*/for(int i=1;i<=max_hp;i++){long long t=-1;for(int j=0;j<m;j++){if(a[j].hit<=0)continue;if(i-a[j].hit<=0){if(t==-1||t>a[j].spend){t=a[j].spend;}continue;}if(t==-1||t>dp[i-a[j].hit][k_def]+a[j].spend){t=dp[i-a[j].hit][k_def]+a[j].spend;}}dp[i][k_def]=t;}}for(int i=0;i<=max_hp;i++){for(int j=0;j<=10;j++){ans+=(dp[i][j]*num[i][j]);}}printf("%I64d\n",ans);}}

總結(jié)

以上是生活随笔為你收集整理的2017百度之星 资格赛 1003 度度熊与邪恶大魔王（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。