TRIBE - Bộ lạc

Tác giả: ll931110

Ngôn ngữ: C++

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int f[52][52][52];
vector< pair<string,int> > v;
string s[52];
int a[52],b[52],val[52];
int n,maxx,maxy,maxz;

int rec(int x,int y,int z)
{
     if (f[x][y][z] != -1) return f[x][y][z];
     int best = 0;
     if (!z) 
     {
        for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,val[i]);
     }
     else
       for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i]) best = max(best,rec(x - a[i],y - b[i],z - 1) + val[i]);
     f[x][y][z] = best;  return best;
};

void track(int x,int y,int z,bool first)
{
     if (!f[x][y][z]) return;
     if (!first) printf(" ");
     if (!z)
     {
       for (int i = 0; i < n; i++) if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i])
       {
           cout << s[i]; break;
       };
     }
     else
     for (int i = 0; i < n; i++) 
       if (x >= a[i] && y >= b[i] && f[x][y][z] == val[i] + rec(x - a[i],y - b[i],z - 1))
       {
             cout << s[i];  track(x - a[i],y - b[i],z - 1,false);  break;       
       };
};

int main()
{
//    freopen("tribe.in","r",stdin);
//    freopen("tribe.ou","w",stdout);
    scanf("%d", &n);
    scanf("%d %d %d", &maxx, &maxy, &maxz);
    for (int i = 0; i < n; i++)
    {
        string st;  int k;
        cin >> st >> k;
        v.push_back(make_pair(st,k));        
    };
    sort(v.begin(),v.end());
    for (int i = 0; i < n; i++)
    {
        a[i] = 0;  b[i] = 0; s[i] = v[i].first; val[i] = v[i].second;
        for (int j = 0; j < s[i].size(); j++) if (s[i][j] == 'a') a[i]++; else b[i]++;
    };
    memset(f,-1,sizeof(f));
    int tmp = rec(maxx,maxy,maxz);
    track(maxx,maxy,maxz,true);  
};

Download