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

#代码：

#include<bits/stdc++.h>
#define MAXN 1050


using namespace std;
int n,m;
long long int dp[MAXN][11]={0};//把防御值为j的怪物，生命值打掉i需要消耗的最少的水晶数。
long long int num[MAXN][11]={0};//num[i][j]生命值为i，防御为j的怪物个数
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++)//找到最小花费 { 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);
        }

}