WA#5,萌新真调不出来了呜呜呜
查看原帖
WA#5,萌新真调不出来了呜呜呜
68882
灵华楼主2022/9/20 14:20

帮忙看一下呗

#include <iostream>
#include <cstring>
using namespace std ;

const int N = 4005 , INF = 0x3f3f3f3f ;
const int cost[] = { 0 , 100 , 50 , 20 , 10 , 5 , 1 } ;
int x1 , x2 , x3 , a[4][7] , s[4] , sum , f[7][N][N] ;

inline void cax ( int &x , int y ) { x = min ( x , y ) ; }

int main ( ) {
	cin >> x1 >> x2 >> x3 ;
	for ( int j = 1 ; j <= 3 ; ++ j ) {
		for ( int i = 1 ; i <= 6 ; ++ i )
			cin >> a [ j ] [ i ] , s [ j ] += a [ j ] [ i ] * cost [ i ] ;
	}
	sum = s [ 1 ] + s [ 2 ] + s [ 3 ] ;
	sum <<= 1 ;
	memset ( f , 0x3f , sizeof ( f ) ) ;
	f [ 0 ] [ s [ 1 ] ] [ s [ 2 ] ] = 0 ;
	for ( int i = 1 ; i <= 6 ; ++ i ) {
		int val = cost [ i ] ;
		for ( int u = 0 ; u <= sum ; ++ u ) {
			for ( int v = 0 ; v <= sum ; ++ v ) {
				if ( f [ i - 1 ] [ u ] [ v ] >= INF ) continue ;
				int w = f [ i - 1 ] [ u ] [ v ] ;
				cax ( f [ i ] [ u ] [ v ] , w ) ;
				for ( int l = 1 ; l <= a [ 1 ] [ i ] ; ++ l )
					for ( int k = 0 ; k <= l ; ++ k )
						cax ( f [ i ] [ u - l * val ] [ v + k * val ] , w + l ) ;
				for ( int l = 1 ; l <= a [ 2 ] [ i ] ; ++ l )
					for ( int k = 0 ; k <= l ; ++ k )
						cax ( f [ i ] [ u + k * val ] [ v - l * val ] , w + l ) ;
				for ( int l = 1 ; l <= a [ 3 ] [ i ] ; ++ l )
					for ( int k = 0 ; k <= l ; ++ k )
						cax ( f [ i ] [ u + k * val ] [ v + ( l - k ) * val ] , w + l ) ;
			}
		}
	}
	if ( f [ 6 ] [ s [ 1 ] - x1 + x3 ] [ s [ 2 ] - x2 + x1 ] >= INF )
		puts ( "impossible" ) ;
	else cout << f [ 6 ] [ s [ 1 ] - x1 + x3 ] [ s [ 2 ] - x2 + x1 ] << "\n" ;
	return 0 ;
}

从bzoj上套到的#5的数据:

146 -158 194
1 2 4 0 3 27
1 0 1 0 2 11
1 4 3 0 9 21
12

求助路过大佬

2022/9/20 14:20
加载中...