Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
145985 | 梁乃元 | 邮票面值问题 | C++ | 通过 | 100 | 192 MS | 276 KB | 774 | 2024-05-06 13:47:43 |
# include <bits/stdc++.h> using namespace std ; int n , k , f [55] = { 0 , 1 } , stamp [55] , maxn ; void dfs ( int idx ) { if ( idx > k ) { int dp [5100] = { 0 } ; int i = 0 ; while ( dp [i] <= n ) { i ++ ; dp [i] = 0x3f3f3f3f ; for ( int j = 1 ; j <= k && i - f [j] >= 0 ; j ++ ) { dp [i] = min ( dp [i] , dp [i - f [j]] + 1 ) ; } } if ( i - 1 > maxn ) { memcpy ( stamp , f , sizeof ( f ) ) ; maxn = i - 1 ; } return ; } for ( int i = f [idx - 1] + 1 ; i <= f [idx - 1] * n + 1 ; i ++ ) { f [idx] = i ; dfs ( idx + 1 ) ; } } int main ( ) { cin >> n >> k ; dfs ( 2 ) ; for ( int i = 1 ; i <= k ; i ++ ) { cout << stamp [i] << ' ' ; } cout << maxn << endl ; return 0 ; }