队伍配置

题目链接

题意

给n个人，每个人有花费和贡献
m个装备，每个装备也有花费和贡献。
每个人最多只能够有一件装备。每个装备只能给一个人。
最多可以选5个人。
选出来的人和装备的花费和不能超过d。
求可以选出来的最大的贡献和是多少。
总结：三个条件:
选的装备的数量不能多余人的数量。
花费不能多余d
最多选5个人。

数据范围：
n,m <= 300
d <= 128

题解。

肯定可以想得到背包。但是我还是不会，我好菜。
dp[i][j][k] 表示花费为i的时候选j个人和k件装备的最大的贡献是多少。
这个表达的状态我是想到了，但是不会转移。。
怎么转移呢？
可以先算出不要装备的时候的贡献。
然后把装备加进去。
不加装备这个就是01背包了。

for (int i = 1; i <= n; i ++ )
	{
   
		for(int j = d; j >= a[i].sd; j -- )
		{
   
			for (int k = 1; k <= 5; k ++ )
			{
   
				dp[j][k][0] = max(dp[j - a[i].sd][k - 1][0] + a[i].st,dp[j][k][0]);
				ans = max(ans,dp[j][k][0]);
				// printf("%d %d %d\n",j,k,dp[j][k][0]);
			}
		}
	}

然后 把装备加进去。

for (int i = 1; i <= m; i ++ )
	{
   
		for (int j = d; j >= b[i].sd; j -- )
		{
   
			for (int k = 1; k <= 5; k ++ )
			{
   
				for (int p = 1; p <= k; p ++ )
				{
   
					dp[j][k][p] = max(dp[j][k][p],dp[j - b[i].sd][k][p - 1] + b[i].st);
					ans = max(ans,dp[j][k][p]);
					// printf("%d\n",ans);
				}
			}
		}
	}

代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 2e6+5;

pii a[maxn];
pii b[maxn];
int dp[150][10][10];

int main()
{
   
	int n,m,d;
	scanf("%d%d%d",&n,&m,&d);
	for (int i = 1; i <= n; i ++ )
	{
   
		scanf("%d%d",&a[i].st,&a[i].sd);
	}
	for (int i = 1; i <= m; i ++ )
	{
   
		scanf("%d%d",&b[i].st,&b[i].sd);
	}
	int ans = 0;
	for (int i = 1; i <= n; i ++ )
	{
   
		for(int j = d; j >= a[i].sd; j -- )
		{
   
			for (int k = 1; k <= 5; k ++ )
			{
   
				dp[j][k][0] = max(dp[j - a[i].sd][k - 1][0] + a[i].st,dp[j][k][0]);
				ans = max(ans,dp[j][k][0]);
				// printf("%d %d %d\n",j,k,dp[j][k][0]);
			}
		}
	}
	// for(int j = d; j >= 0; j -- )
	// {
   
	// for (int k = 1; k <= 5; k ++ )
	// {
   
	// // dp[j][k][0] = max(dp[j - a[i].sd][k - 1][0] + a[i].st,dp[j][k][0]);
	// printf("%d %d %d\n",j,k,dp[j][k][0]);
	// }
	// }
	
	for (int i = 1; i <= m; i ++ )
	{
   
		for (int j = d; j >= b[i].sd; j -- )
		{
   
			for (int k = 1; k <= 5; k ++ )
			{
   
				for (int p = 1; p <= k; p ++ )
				{
   
					dp[j][k][p] = max(dp[j][k][p],dp[j - b[i].sd][k][p - 1] + b[i].st);
					ans = max(ans,dp[j][k][p]);
					// printf("%d\n",ans);
				}
			}
		}
	}
	// for (int i = 1; i <= d; i ++ )
	// {
   
	// for (int j = 1; j <= 5; j ++ )
	// {
   
	// for (int k = 1; k <= j; k ++ )
	// printf("%d %d %d %d\n",i,j,k,dp[i][j][k]);
	// }
	// }
	printf("%d\n",ans);
}