求神（PID:667）
#include<cstdio>
#include<iostream>
using namespace std;
int max(int x,int y){
return x>y?x:y;
}
int a,n,b;
int va[10050],vb[10050],w[10050];
int f[10050][10050],i,j,k;
void out(int jb){
bool first=true;
if(jb==0){
cout<<"ling";
return ;
}
if(jb>1000){
switch(jb/1000){
case 1:cout<<"yi qian";break;
case 2:cout<<"liang qian";break;
case 3:cout<<"san qian";break;
case 4:cout<<"si qian";break;
case 5:cout<<"wu qian";break;
case 6:cout<<"liu qian";break;
case 7:cout<<"qi qian";break;
case 8:cout<<"ba qian";break;
case 9:cout<<"jiu qian";break;
}
jb%=1000;
if(jb>=100) cout<<" ";
else cout<<" ling ";
first=false;
}
if(jb>100){
switch(jb/100){
case 1:cout<<"yi bai";break;
case 2:cout<<"liang bai";break;
case 3:cout<<"san bai";break;
case 4:cout<<"si bai";break;
case 5:cout<<"wu bai";break;
case 6:cout<<"liu bai";break;
case 7:cout<<"qi bai";break;
case 8:cout<<"ba bai";break;
case 9:cout<<"jiu bai";break;
}
jb%=100;
if(jb>=10) cout<<" ";
else cout<<" ling ";
first=false;
}
if(jb>10){
switch(jb/10){
case 1:
if(first) cout<<"shi";
else cout<<"yi shi";
break;
case 2:cout<<"er shi";break;
case 3:cout<<"san shi";break;
case 4:cout<<"si shi";break;
case 5:cout<<"wu shi";break;
case 6:cout<<"liu shi";break;
case 7:cout<<"qi shi";break;
case 8:cout<<"ba shi";break;
case 9:cout<<"jiu shi";break;
}
jb%=10;
if(jb) cout<<" ";
}
switch(jb){
case 1:cout<<"yi";break;
case 2:cout<<"er";break;
case 3:cout<<"san";break;
case 4:cout<<"si";break;
case 5:cout<<"wu";break;
case 6:cout<<"liu";break;
case 7:cout<<"qi";break;
case 8:cout<<"ba";break;
case 9:cout<<"jiu";break;
}
}
int main(){
cin>>a>>n>>b;
for(i=1;i<=n;i++){
cin>>va[i]>>w[i]>>vb[i];
for(j=a;j>=va[i];j--)
for(k=b;k>=vb[i];k--)
f[j][k]=max(f[j][k],f[j-va[i]][k-vb[i]]+w[i]);
}
out(f[a][b]);
return 0;
}