本文主要是介绍csu(背包的变形题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
这是一道背包的变形题目。好题呀
题意:给n个怪物，m个人，每个人的魔法消耗和魔法伤害不同，求打死所有怪物所需的魔法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
//#include<u>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define ll long long
#define inf 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int ph[105];//每个怪物的ph
vector<pair<int ,int> > a[2];//a[0]放攻击范围为All的怪物信息，a[1]放攻击范围为Single的怪物信息
int dp[2][100005];//dp[0][i]表示攻击范围为All的人使用i的魔法能对每个怪物产生的伤害，dp[1][i]是针对攻击范围为Single的人
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);ios::sync_with_stdio(false);int n,m;//n个怪物，m个人while(cin>>n){a[0].clear();a[1].clear();int mp,damage;int i,j,k;char str[20];for(i = 0; i < n; i++)cin>>ph[i];cin>>m;bool flag = 0;for(i = 0; i < m; i++){cin>>str>>mp>>str>>damage;if(str[0] == 'A')a[0].push_back(make_pair(mp,damage));else a[1].push_back(make_pair(mp,damage));if(mp == 0 && damage > 0) flag = 1;//如果有人的魔法消耗为0，并且输出伤害大于0，那么无需消耗魔法}if(flag) { cout<<"0\n";continue;}memset(dp,0,sizeof(dp));for(i = 0; i < 2; i++){int len = a[i].size();for(j = 0; j < len; j++)//这里相当于是完全背包for(k = a[i][j].first; k < 100002; k++)dp[i][k] = max(dp[i][k], dp[i][k - a[i][j].first] + a[i][j].second);}ll ans = (1ll<<61),temp;for(i = 0; i < ans; i++)//遍历消耗魔法为i，攻击范围是ALL的情况{temp = i;for(j = 0; j < n; j++){ll k = ph[j] - dp[0][i];//k是剩下的血量if(k <= 0) continue;temp += (lower_bound(dp[1],dp[2],k) - dp[1]); //lower_bound 查找第一个插入元素但不影响序列有序性的位置， }}ans = min(ans,temp);}cout<<ans<<endl;}return 0;
}
这篇关于csu(背包的变形题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
