ZUCC jiubei and TFT

题意：

jiubei的朋友们很喜欢玩TFT（Teamfight Tactics）。和大多数自走棋游戏一样，在TFT中有很多不同种类的羁绊，每个被激活的羁绊会给予部分上场的英雄战斗力加成。jiubei的备战区有一些英雄，他想知道怎么样能够使总战斗力最高的阵容得以上场。为了简化问题，假设jiubei一共有个英雄，只有个英雄可以上场。另外，一共有种羁绊。每个英雄属于某些羁绊，在上场的英雄中，如果属于某个羁绊的英雄数量达到或者超过一些特定值，就可以使这个羁绊触发，并使属于这个羁绊的所有上场英雄提高一定的战斗力。

题解：

直接暴力做，一开始题目意思没理解。

#include<bits/stdc++.h>
using namespace std;
const int maxn=45;
typedef long long ll;
int a[maxn][maxn];//第i种羁绊j个英雄加成多少
int b[maxn][maxn];//第i种英雄是否属于第j种羁绊
int c[maxn];//第i种英雄的战斗力
int N,M,K;
unordered_map<string,int> pos;
ll mmax=-1;
vector<int> tmp,path;
void dfs (int v,int cnt) {
    if (cnt==K) {
        ll ans=0;
        int num[25]={0};
        for (int i=0;i<tmp.size();i++) {
            ans+=c[tmp[i]];
            for (int j=1;j<=M;j++) 
                num[j]+=b[tmp[i]][j];
        } 
        for (int i=1;i<=M;i++) {
            ll Max=0;
            for (int j=1;j<=6;j++) {
                Max=max(Max,(ll)a[i][j]*num[i]*(num[i]>=j));
            }
            ans+=Max;
        }
        if (ans>mmax) {
            mmax=ans;
            path=tmp;
        }
        return;
    }
    v++;
    while (v<=N+M+1) {
        tmp.push_back(v);
        dfs(v,cnt+1);
        tmp.pop_back();
        v++;
    }
}
int main () {
    scanf("%d%d%d",&N,&M,&K);
    string s;
    int t,x,y;
    for (int i=1;i<=M;i++) {
        cin>>s;
        pos[s]=i;
        scanf("%d",&t);
        for (int j=0;j<t;j++) {
            scanf("%d%d",&x,&y);
            a[i][x]=y;
        }
    }
    for (int i=1;i<=N;i++) {
        cin>>s;
        pos[s]=M+1+i;
        scanf("%d",&x);
        c[pos[s]]=x;
        scanf("%d",&t);
        for (int j=0;j<t;j++) {
            string s1;
            cin>>s1;
            b[pos[s]][pos[s1]]=1;
        }
    }
    dfs(M+1,0);
    printf ("%lld\n",mmax);
    return 0;
}

原文链接: https://www.cnblogs.com/zhanglichen/p/12463719.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/372576

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

ZUCC jiubei and TFT

相关推荐