[HDU P6082]度度熊与邪恶大魔王

原题链接

有点意外的DP
其实一开始的思路也是背包
但是思考方向的不对
后来看了题解

就是
DP[i][j]表示在防御力为i的情况下打出j点伤害所需的最小晶石数
枚举魔法的时候
如果直接能打掉就用这招消耗的晶石数和原来取min
不能的话就是dp[i][j]=min(dp[i][j],dp[i][j-hurt]+kei[k])

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<ctime>
#define LL long long
#define MOD 1000000007
using namespace std;LL n,m,maxa,maxb,maxp,i,j,k,hur; 
LL ans,dp[15][1005],a[100005],b[100005],kei[1005],p[1005];int main() 
{while(scanf("%lld%lld",&n,&m)!=EOF){ans=0;maxa=0;maxb=0;maxp=0;memset(dp,127,sizeof(dp));for(i=1;i<=n;i++){scanf("%lld%lld",&a[i],&b[i]);maxb=max(maxb,b[i]);maxa=max(maxa,a[i]);            }for(i=1;i<=m;i++){scanf("%lld%lld",&kei[i],&p[i]);maxp=max(maxp,p[i]);        }if(maxb>=maxp){printf("-1\n");continue;}for(i=0;i<=maxb;i++)for(j=1;j<=maxa;j++)for(k=1;k<=m;k++){if(p[k]<=i) continue;if(p[k]-i>=j) dp[i][j]=min(dp[i][j],kei[k]);if(p[k]-i<j){hur=p[k]-i;dp[i][j]=min(dp[i][j],dp[i][j-hur]+kei[k]);}}               for(i=1;i<=n;i++)ans+=dp[b[i]][a[i]];printf("%lld\n",ans);}return 0;
}

[HDU P6082]度度熊与邪恶大魔王

原题链接

有点意外的DP
其实一开始的思路也是背包
但是思考方向的不对
后来看了题解

就是
DP[i][j]表示在防御力为i的情况下打出j点伤害所需的最小晶石数
枚举魔法的时候
如果直接能打掉就用这招消耗的晶石数和原来取min
不能的话就是dp[i][j]=min(dp[i][j],dp[i][j-hurt]+kei[k])

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#include<climits>
#include<string>
#include<cstdlib>
#include<ctime>
#define LL long long
#define MOD 1000000007
using namespace std;LL n,m,maxa,maxb,maxp,i,j,k,hur; 
LL ans,dp[15][1005],a[100005],b[100005],kei[1005],p[1005];int main() 
{while(scanf("%lld%lld",&n,&m)!=EOF){ans=0;maxa=0;maxb=0;maxp=0;memset(dp,127,sizeof(dp));for(i=1;i<=n;i++){scanf("%lld%lld",&a[i],&b[i]);maxb=max(maxb,b[i]);maxa=max(maxa,a[i]);            }for(i=1;i<=m;i++){scanf("%lld%lld",&kei[i],&p[i]);maxp=max(maxp,p[i]);        }if(maxb>=maxp){printf("-1\n");continue;}for(i=0;i<=maxb;i++)for(j=1;j<=maxa;j++)for(k=1;k<=m;k++){if(p[k]<=i) continue;if(p[k]-i>=j) dp[i][j]=min(dp[i][j],kei[k]);if(p[k]-i<j){hur=p[k]-i;dp[i][j]=min(dp[i][j],dp[i][j-hur]+kei[k]);}}               for(i=1;i<=n;i++)ans+=dp[b[i]][a[i]];printf("%lld\n",ans);}return 0;
}