1003度度熊与邪恶大魔王

Accepts: 1503Submissions: 9026Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)

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

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

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

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

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

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

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

【解析】：完全背包打表，把每种可能的怪兽都计算出来dp[i][j]表示血量为i，防御力为j的怪兽最少消耗的水晶数【代码】：

#include <stdio.h>
#include <string.h>  
#include <iostream>  
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;

ll a[120000],b[120000];
ll k[1200],p[1200];
ll dp[1200][22];//dp[i][j]生命为i防御为j的怪兽所需水晶
int main()
{
int n,m;
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
scanf("%d%d",&a[i],&b[i]);

ll maxp=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&k[i],&p[i]);
maxp=max(maxp,p[i]);
}
int flag=0;
for(int i=0;i<n;i++)
{
if(b[i]>=maxp){
flag=1;
break;
}
}
if(flag){
puts("-1");
continue;
}
memset(dp,INF,sizeof(dp));
for(int j=0;j<=12;j++)
dp[0][j]=0;
for(int x=0;x<m;x++)
{
for(int j=0;j<=10;j++)
for(int i=0;i<=1000;i++)
{
if(p[x]<=j)continue;
if(i<=p[x]-j)//不堪一击or恰好一击 
dp[i][j]=min(dp[i][j],k[x]);
else if(dp[i][j]>dp[i-(p[x]-j)][j]+k[x])
dp[i][j]=dp[i-(p[x]-j)][j]+k[x];
}
}
ll sum=0;
for(int i=0;i<n;i++)
{
sum+=dp[a[i]][b[i]];
}
cout<<sum<<endl;
}
return 0;
}

1004度度熊的午饭时光

Accepts: 235Submissions: 3808Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)

度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。

百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。

但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)

【解析】：01背包+记录路径。把所有可以得到最高得分的方案路径记录下来，取其中序号和最小的，对于序号和相等的，再比较出字典序靠前的【代码】；

#include <stdio.h>
#include <string.h>  
#include <iostream>  
#include <algorithm> 
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f;

ll dp[1200];
ll v[1200],w[1200];
bool path[1100][1100];
int a[1005][120];
int check(int ii,int jj)//字典序比较函数 
{
int t1=a[ii][0];
int t2=a[jj][0];
for(int i=1,j=1;i<=t1&&j<=t2;i++,j++)
{
if(a[ii][i]!=a[jj][j])
return a[ii][i]-a[jj][j];
}
return 0;
}
int main()
{
ll T,B,N;
int rrr=1;
cin>>T;
while(T--)
{
scanf("%lld %lld",&B,&N);
memset(path,0,sizeof(path));
memset(dp,0,sizeof(dp));
for(int i=1;i<=N;i++)
{
ll val,wei;
scanf("%lld %lld",&val,&wei);
v[i]=val;
w[i]=wei;
for(int j=B;j>=wei;j--){
if(dp[j]<dp[j-wei]+val){
dp[j]=dp[j-wei]+val;
path[i][j]=1;//j包顶i
}
}
}
ll maxv=0;
for(int j=0;j<=B;j++)
maxv=max(maxv,dp[j]);//最高得分

ll dexsum=INF;
int k=0,mark=0;
for(int jj=B;jj>=0;jj--)
{
if(dp[jj]==maxv)
{
ll sum=0;//序号和
int top=1;
int i=N,j=jj;
while(i>=1&&j>=0)
{  
    if(path[i][j])//物品i在j里
    {
a[k][top++]=i;
sum+=i;
        j-=w[i];  //读完了物品i，找下一个背包状态   
    }  
    i--;   
}
a[k][0]=top-1;//个数
sort(a[k]+1,a[k]+1+a[k][0]);
if(dexsum>sum){
dexsum=sum;
mark=k;//第k组
}
else if(dexsum==sum&&check(k,mark)<0){
dexsum=sum;
mark=k;//第k组
}
k++;
}
}


ll val=0,cost=0;
int top=a[mark][0];
sort(a[mark]+1,a[mark]+1+a[mark][0]);
for(int i=1;i<=top;i++)
{
val+=v[a[mark][i]];
cost+=w[a[mark][i]];
}
printf("Case #%d:\n",rrr++);
printf("%lld %lld\n",val,cost);
for(int i=1;i<top;i++)
printf("%d ",a[mark][i]);
if(top>=1)
printf("%d\n",a[mark][top]);
}
}

秒客网

2017百度之星资格赛题解

1003度度熊与邪恶大魔王

1004度度熊的午饭时光

相关文章