CF687C 硬幣面額

1 CF687C題目連結：https://codeforces.com/problemset/problem/687/c2 題目描述

時間限制

3 題解

我們觀察數據範圍，發現

接下來我們來研究轉移。一共有兩種方案：第

這裡我們用

對於第二種情況，我們的轉移是：

這個意義就相對來說更簡單了，我們不用第

這裡我們發現：第一維其實與普通背包中的第一位差不多，可以採用滾動數組滾掉。這樣

4 代碼（空格警告）：

#include <iostream>
using namespace std;
const int N = 505;
int n, k, ans;
int c[N], dp[N][N], s[N];
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> c[i];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = k; j >= c[i]; j--)
        {
            for (int l = k; l >= 0; l--)
            {
                if (l >= c[i]) dp[j][l] |= dp[j - c[i]][l - c[i]];
                dp[j][l] |= dp[j-c[i]][l];
            }
        }
    }
    for (int i = 0; i <= k; i++) if (dp[k][i]) s[++ans] = i;
    cout << ans << '\n';
    for (int i = 1; i <= ans; i++) cout << s[i] << " ";
    return 0;
}
歡迎關注