CFR 189 A. Cut Ribbon ( DP )
Problem - 189A - Codeforces
題意:
給繩子長度和三種可裁切的長度,一個合法的裁切是所有結果的繩子的長度都是三種可裁切的長度之一,求最多可能裁切的繩子數。
解法:
dp[ i ] : 考慮長度 i 的繩子已裁切完,此時最多的繩子數。
dp[ i ] = max{ dp[ i - A ], dp[ i - B ], dp[ i - C ] }
int N, A, B, C; void init(){ cin >> N >> A >> B >> C; } void preprocess(){ } void solve(){ vi dp( N + 1, -INF ); dp[ 0 ] = 0; for( int i = 0; i < N; ++i ){ if( i + A <= N ) upmax( dp[ i + A ], dp[ i ] + 1 ); if( i + B <= N ) upmax( dp[ i + B ], dp[ i ] + 1 ); if( i + C <= N ) upmax( dp[ i + C ], dp[ i ] + 1 ); } cout << dp[ N ] << endl; }