40分求助
查看原帖
40分求助
283541
harvey2019楼主2024/10/25 18:44

首先我没算最小值,没算最小值应该是拿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;
}
2024/10/25 18:44
加载中...