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);
};