NC14699. 队伍配置
描述
输入描述
第1行输入三个整数n，m，d，代表玩家仓库的从者数量、概念礼装数量和cost上限值。第2-n+1行，每行输入两个整数a1，b1，表示第i个从者的ATK值和cost值。第n+2-n+m+1行，每行输入两个整数a2，b2，表示第i个概念礼装的ATK值和cost值。数据保证：0<n,m≤300，25≤d≤138，1000≤a1≤15488，500≤a2≤2500，3≤b1,b2≤12
输出描述
输出一行，一个整数，代表可以凑出的最大ATK值。
示例1
输入:
4 2 25 2001 5 2002 5 2003 5 4010 10 2004 10 2005 10
输出:
10016
说明:
派上前4名从者，最大ATK值=2001+2002+2003+4010=10016（cost总值为25=玩家cost上限）C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2022-08-24 08:36:22
#include<bits/stdc++.h>
using namespace std;
int n,m,d,atk,cost,f[10][200],ans;
int main()
{
cin>>n>>m>>d;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&atk,&cost);
for(int j=d;j>=cost;j--)
for(int k=5;k>=1;k--)
f[k][j]=max(f[k][j],f[k-1][j-cost]+atk);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&atk,&cost);
for(int j=d;j>=cost;j--)
for(int k=0;k<=5;k++)
{
f[k][j]=max(f[k][j],f[k+1][j-cost]+atk);
ans=max(f[k][j],ans);
}
}
cout<<ans;
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 412K, 提交时间: 2023-01-15 00:24:25
#include<iostream>
using namespace std;
int f[607][10][10];
int main()
{
int n,m,d,x,y,ans=-1;
cin>>n>>m>>d;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
for(int j=d;j>=y;j--)
for(int k=1;k<=5;k++)
ans=max(ans,f[j][k][0]=max(f[j][k][0],f[j-y][k-1][0]+x));
}
for(int i=1;i<=m;i++)
{
cin>>x>>y;
for(int j=d;j>=y;j--)
for(int k=1;k<=5;k++)
for(int l=1;l<=k;l++)
ans=max(ans,f[j][k][l]=max(f[j][k][l],f[j-y][k][l-1]+x));
}
cout<<ans<<endl;
return 0;
}