TRIBE - Bộ lạc
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
int n,x,y,z,gt[51],soa[51],sob[51],f[51][51][55],temp;
string s[51],the1,the2,the;
int main(){
//freopen("TRIBE.in","r",stdin);
scanf("%d %d %d %d",&n,&x,&y,&z);
for(int i = 1;i<=n;i++)
cin>>s[i]>>gt[i];
memset(f,0,sizeof(f));
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++){
the1 = s[i]+' '+s[j];
the2 = s[j]+' '+s[i];
if(the1.compare(the2)<0){
the = s[i];
s[i] = s[j];
s[j] = the;
temp = gt[i];
gt[i] = gt[j];
gt[j] = temp;
}
}
for(int i = 1;i<=n;i++){
soa[i] = 0; sob[i] = 0;
for(int j = 0;j<s[i].length();j++)
if(s[i][j]=='a') soa[i]++;
else sob[i]++;
}
for(int i = 1;i<=z+1;i++){
for(int tx = 0;tx<=x;tx++)
for(int ty=0;ty<=y;ty++){
f[tx][ty][i] = f[tx][ty][i-1];
for(int j = 1;j<=n;j++)
if(tx-soa[j]>=0 && ty-sob[j]>=0)
f[tx][ty][i] >?= f[tx-soa[j]][ty-sob[j]][i-1]+ gt[j];
}
}
z++;
int run = f[x][y][z];
//printf("%d\n",run);
//while(f[x][y][z] == f[x][y][z-1]) z--;
int l;
while(z>0){
l = z;
// printf("%d %d %d %d\n",run,x,y,z);
for(int i = 1;i<=n;i++){
if(x>=soa[i] && y>=sob[i])
if(run == f[x-soa[i]][y-sob[i]][z-1]+gt[i]){
cout<<s[i]<<" ";
run -= gt[i];
x -= soa[i];
y -= sob[i];
z--;
break;
}
}
if(l==z) z--;
// printf("%d %d %d %d\n",run,x,y,z);
//getch();
}
// getch();
}