宝石（暴力搜）

宝石

Time Limit : 3000/1000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 0   Accepted Submission(s) : 0

Times New Roman | Verdana | Georgia

← →

Problem Description

有一个商人喜欢收集一些宝石，有一天他得到了三种十分好看的宝石，把它们分别取名为 M, V, P。它们对应的单个价值为 DM, DV, DP。宝石可以两两合成，如M, V可以合成为新的高级宝石C, 价值为DC。 M, P 可以合成为新的高级宝石H，价值为DH。V, P 可以合成为新的高级宝石Y，价值为DY。最后，M, V, P 一起可以合成最高级宝石W， 价值为 DW。
现在，商人有一篮子宝石，以一个字符串表示。商人想知道如何合成这一篮子宝石，使得这一篮子的宝石价值和最大，每一个单个宝石最多只能合成一次或者不合成。求这一篮子的宝石的价值最大值。

Input

多组测试样例
每组测试样例第一行输入7个整数，分别表示DM, DV, DP, DC, DH, DY, DW。第二行输入一个字符串，如VVP, MVVPMMP等。所有整数的绝对值小于100。字符串长度小于等于40且不为空。 

Output

输出一个整数，表示这一篮子的宝石的最大价值。

Sample Input

1 1 1 2 2 2 5 PVM -5 1 1 1 1 1 1 MMM

Sample Output

5 -15

#include<stdio.h>
int main(){
	int dm, dv, dp, dc, dh, dy, dw;
	int cc,ch,cy,cw;
	int fm,fv,fp;
	int i,max;
	int tm,tv,tp,t;
	char str[50];
	while(~scanf("%d%d%d%d%d%d%d",&dm,&dv,&dp,&dc,&dh,&dy,&dw)){
		scanf("%s",str);
		fm=fv=fp=i=0;
		while(str[i]){
			if(str[i]=='M')fm++;
			else if(str[i]=='V')fv++;
			else if(str[i]=='P')fp++;
			i++;
		}
		max=-200000000;
		for(cc=0;cc<=20;cc++){
			for(ch=0;ch<=20;ch++){
				for(cy=0;cy<=20;cy++){
					for(cw=0;cw<=20;cw++){
						tm=fm-cc-ch-cw;
						tv=fv-cc-cy-cw;
						tp=fp-ch-cy-cw;
						if(tm>=0&&tv>=0&&tp>=0){
							t=tm*dm+tv*dv+tp*dp;
							t+=cc*dc+ch*dh+cy*dy+cw*dw;
							if(max<t)max=t;
						}
					}
				}
			}
		}
		printf("%d\n",max);
	}
	
}