萌新刚学 OI,dp+dfs 求调。
查看原帖
萌新刚学 OI,dp+dfs 求调。
677831
srds_cbddl楼主2023/7/17 20:00
#include <bits/stdc++.h>
using namespace std;

int n, k, ans = 0;
int a[15], b[15], dp[15];

inline int dp_solve(int k1) {
    memset(dp, 63, sizeof dp);
	dp[0] = 0;
    for (int i = 1; i <= k1; i ++)
        for (int j = a[i]; j <= a[i] * n; j ++)
            dp[j] = min(dp[j], dp[j - a[i]] + 1);
    for(int i = 1; i < 15; i ++)
        if(dp[i] > n)
			return i - 1;
}

void dfs(int k1) {
    if(k1 > k) {
        int end = dp_solve(k - 1);
        if (end > ans) {
            ans = end;
            memcpy(b, a, sizeof a);
        }
        return ;
    }
    int end = dp_solve(k1 - 1);	
    for (int i = a[k1 - 1] + 1; i <= end + 1; i ++) {
        a[k1] = i;
		dfs(k1 + 1);
    }
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k;

    a[1] = 1;
    dfs(2);

    for(int i = 1; i <= k; i ++)
		cout << b[i] << ' ';
    cout << '\n' << "MAX=" << ans; 
    return 0; 
}
2023/7/17 20:00
加载中...