如何解决2017百度之星资格赛1003、1004题的算法问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1816个文字，预计阅读时间需要8分钟。
1003 度度熊与恶魔大王 + Accepts: 1503 + Submissions: 9026 + Time Limit: 2000/1000 MS + Memory Limit: 32768/32768 K + Problem Description + 度度熊为拯救可爱的公主，与恶魔大王展开战斗。
1003度度熊与邪恶大魔王
Accepts: 1503
Submissions: 9026
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
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
Copy
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6
Sample Output
Copy
6
18
：
完全背包打表，把每种可能的怪兽都计算出来
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: 235
Submissions: 3808
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。
百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。
但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)
Input
第一行一个整数T，表示T组数据。 每组测试数据将以如下格式从标准输入读入：
B
N
score_1 cost_1
score_2 cost_2
:
score_N cost_N
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。
第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量
从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。
Output
对于每组数据，输出两行： 第一行输出："Case #i:"。i代表第i组测试数据。 第二行输出菜品的总得分和总花费，以空格分隔。 第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。
Sample Input
Copy
2
29
6
9 10
3 4
6 5
7 20
10 9
15 11
0
2
2 23
10 12
Sample Output
Copy
Case #1:
34 29
2 3 5 6
Case #2:
0 0
：
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]);
}
}
本文共计1816个文字，预计阅读时间需要8分钟。
1003 度度熊与恶魔大王 + Accepts: 1503 + Submissions: 9026 + Time Limit: 2000/1000 MS + Memory Limit: 32768/32768 K + Problem Description + 度度熊为拯救可爱的公主，与恶魔大王展开战斗。
1003度度熊与邪恶大魔王
Accepts: 1503
Submissions: 9026
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
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
Copy
1 2
3 5
7 10
6 8
1 2
3 5
10 7
8 6
Sample Output
Copy
6
18
：
完全背包打表，把每种可能的怪兽都计算出来
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: 235
Submissions: 3808
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
度度熊最期待每天的午饭时光，因为早饭菜品清淡，晚饭减肥不敢吃太多（胖纸的忧伤T.T）。
百度食堂的午餐超级丰富，祖国各大菜系应有尽有，度度熊在每个窗口都有爱吃的菜品，而且他还为喜爱的菜品打了分，吃货的情怀呀(>.<)。
但是，好吃的饭菜总是很贵，每天的午饭预算有限，请帮度度熊算一算，怎样打饭才能买到的最好吃的饭菜?(不超过预算、不重样、午餐等分最高的情况下，选择菜品序号加和最小，加和相等时字典序最小的组合)
Input
第一行一个整数T，表示T组数据。 每组测试数据将以如下格式从标准输入读入：
B
N
score_1 cost_1
score_2 cost_2
:
score_N cost_N
第一行，正整数B（0 <= B <= 1000），代表午餐的预算。
第二行，正整数N (0 <= N <= 100)，代表午餐可选的菜品数量
从第三行到第 (N + 2) 行，每行两个正整数，以空格分隔，score_i表示菜品的得分，cost_i表示菜品的价格(0 <= score_i, cost_i <= 100)。
Output
对于每组数据，输出两行： 第一行输出："Case #i:"。i代表第i组测试数据。 第二行输出菜品的总得分和总花费，以空格分隔。 第三行输出所选菜品的序号，菜品序号从1开始，以空格分隔。
Sample Input
Copy
2
29
6
9 10
3 4
6 5
7 20
10 9
15 11
0
2
2 23
10 12
Sample Output
Copy
Case #1:
34 29
2 3 5 6
Case #2:
0 0
：
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]);
}
}