#include <stdio.h>
#include <stdlib.h>
#define N 50

int dp[N][N], a[N], result[N];
char c[N+1];

int compute(int x, int y, char ch){
	if(ch=='t') return x+y;
	else if(ch=='x') return x*y;
}

int main(){
	int i, j, k, t, now, max, n, atem, l, r, count;
	char ctem;
	while(scanf("%d", &n)==1){
        for(i=0; i<n; i++){
			getchar();
			c[i]=getchar();
			scanf("%d", &a[i]);
			
        }
		for(i=0; i<n; i++){
			if(i!=0){
				atem=a[0];
				ctem=c[0];
				for(j=0; j<n-1; j++){
					a[j]=a[j+1];
					c[j]=c[j+1];
				}
				a[j]=atem;
				c[j]=ctem;
			}
			for(j=0; j<n; j++) dp[j][j]=a[j];
			for(k=1; k<n; k++){
				for(j=0; j<n-k; j++){
					l=j; r=j+k;
                    max=compute(dp[l][l], dp[l+1][r], c[l+1]);
					for(t=l+1; t<r; t++){
						now=compute(dp[l][t], dp[t+1][r], c[t+1]);
						if(now>max) max=now;
					}
					dp[l][r]=max;
				}
			}
			result[i]=dp[0][n-1];
		}
		max=result[0];
		for(i=1; i<n; i++){
			if(result[i]>max)
				max=result[i];
		}
		printf("%d\n", max);
		count=0;
		for(i=0; i<n; i++){
            if(result[i]==max){
				if(count>0) printf(" ");
				printf("%d", i+1);
				count++;
            }
		}
		printf("\n");
	}
	return 0;
}

• up (0) wronger 2006-06-16 11:06:35
• Re:一直wa, 这题不是枚举再dp吗? 大虾帮忙看看,感激.(内有代码) (1390) Yuzia 2006-08-12 20:38:10
• 乘法的时候两侧的数有可能都取最小的然后负负为正最大。 (17) 11119999 2006-09-06 10:20:46