首先我没算最小值,没算最小值应该是拿80分吧?为啥我四十。最小值一会再修
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef float fl;
typedef double dou;
const ll inf = 0x3f3f3f3f;
const ll mod = 998244353;
inline ll read()
{
ll ans = 0;
ll f = 1;
char c = getchar();
while( c < '0' || c > '9' )
{
if( c == '-' )
{
f = -1;
}
c = getchar();
}
while( c >= '0' && c <= '9' )
{
ans = ( ans << 3 ) + ( ans << 1 ) + ( c - 48 );
c = getchar();
}
return ans * f;
}
inline void write( ll x )
{
if( x < 0 )
{
putchar( '-' );
x = -x;
}
if( x > 9 )
{
write( x / 10 );
}
putchar( x % 10 + '0' );
}
int dp[101][101],pre[101],a[101],b[101];
bool sign[101],sign1[101];
queue < int > que;
int main()
{
int n = read(),max2 = 0,m = n - 1;
for( int i = 1 ; i <= n ; i++ )
{
char ch;
cin >> ch >> a[i];
if( ch == 't' )
{
sign[i] = 1;
}
}
for( int sc = 1 ; sc <= n ; sc++ )
{
memset( dp , 0 , sizeof dp );
memset( sign1 , 0 , sizeof sign1 );
for( int i = sc + 1 ; i <= n ; i++ )
{
dp[i - sc + 1][i - sc + 1] = a[i];
sign1[i - sc] = sign[i];
}
for( int i = 1 ; i < sc ; i++ )
{
dp[n - sc + i + 1][n - sc + i + 1] = a[i];
sign1[n - sc + i] = sign[i];
}
dp[1][1] = a[sc];
// for( int i = 1 ; i <= n ; i++ )
// {
// cout << dp[i][i] << " " << sign1[i] << endl;
// }
for( int i = 2 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n - i + 1 ; j++ )
{
for( int k = j ; k < j + i - 1 ; k++ )
{
if( sign1[k] )
{
dp[j][j + i - 1] = max( dp[j][j + i - 1] , dp[j][k] + dp[k + 1][j + i - 1] );
}
else
{
dp[j][j + i - 1] = max( dp[j][j + i - 1] , dp[j][k] * dp[k + 1][j + i - 1] );
}
// cout << dp[j][j + i - 1] << " " << i << " " << j << " " << k << endl;
}
}
}
// cout<< endl;
int max1 = 0;
for( int i = 1 ; i <= n ; i++ )
{
max1 = max( max1 , dp[i][i + n - 1] );
}
if( max1 > max2 )
{
while( que.size() ) que.pop();
que.push( sc );
max2 = max1;
}
else if( max1 == max2 )
{
max2 = max1;
que.push( sc );
}
}
cout << max2 << endl;
while( que.size() )cout << que.front() << " ",que.pop();
return 0;
}