描述
沈宝宝的天玄石做的又丑又难看，戴尔廖实在是看不下去了，于是就出手帮助了他。
戴尔廖从怀中掏出了很多块神奇的石头，这些石头都是矿石结晶。每颗矿石结晶拥有着的人之精华，以及的地之精华。
戴尔廖缓缓道：“传说中，只要你拥有的石头的人之精华的和为，你拥有的石头的地之精华的和为，且除以恰好等于，拿这些石头去配比，就能得到完美的天玄石！”
沈宝宝一听，高兴的跳了起来！
戴尔廖说：“不急不急，这些石头我可不能白白给你，第颗石头，你需要付出的代价，我才会给你。”
这时，沈宝宝犯难了，沈宝宝究竟最少需要付出多少的代价，才能配比得到天玄石呢？
输入
第一行一个T，表示有T组测试数据。
接下来每组数据：
第一行为两个整数n和C，表示戴尔廖拥有的矿石结晶个数，以及配比需要的比值C。
接下来n行，每行三个整数，A[i],B[i],C[i],分别表示人之精华、地之精华和购买石头需要的代价。
数据满足：
1<=T<=10
1<=n<=100
1<=A[i],B[i]<=10
1<=c[i]<=10000
1<=C<=100
保证所有数据均为整数。
输出
对于每组数据，输出最少合成天玄石的代价，如果不能合成，输出“ShenBaoBao GG”
样例输入1
2
1 1
1 2 1
3 2
3 2 2
3 1 3
3 1 6
样例输出1
ShenBaoBao GG
5
思路：
dp[j][k]表示能量用了j的人之精华，k的地之精华的最小花费。
转移：dp[j][k] = min(dp[j][k],dp[j-a[i]][k-b[i]]+c[i]);
注意，这是一个01背包，所以你得倒着枚举这个状态，以保证状态不会覆盖。（或者你直接三维状态表示也可以。）
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define mem(a) memset(a,0,sizeof(a)) 5 #define mp(x,y) make_pair(x,y) 6 const int INF = 0x3f3f3f3f; 7 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 8 inline ll read(){ 9 ll x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 12 return x*f; 13 } 14 ////////////////////////////////////////////////////////////////////////// 15 const int maxn = 1e3+10; 16 17 int n,C,a[105],b[105],c[105]; 18 int dp[maxn][maxn]; 19 20 int main(){ 21 int T = read(); 22 while(T--){ 23 memset(dp,INF,sizeof(dp)); 24 cin >> n >> C; 25 for(int i=1; i<=n; i++) 26 cin >> a[i] >> b[i] >> c[i]; 27 dp[0][0] = 0; 28 for(int i=1; i<=n; i++) 29 for(int j=maxn-1; j>=0; j--) 30 for(int k=maxn-1; k>=0; k--) 31 if(j>=a[i]&&k>=b[i]) 32 dp[j][k] = min(dp[j][k],dp[j-a[i]][k-b[i]]+c[i]); 33 34 int ans = INF; 35 for(int i=1; i<maxn; i++) 36 for(int j=1; j<maxn; j++){ 37 if(i%j==0 && i/j==C){ 38 ans = min(ans,dp[i][j]); 39 } 40 } 41 if(ans == INF) 42 cout << "ShenBaoBao GG "; 43 else 44 cout << ans << endl; 45 } 46 47 return 0; 48 }