程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> codeforces 543A 完全背包

codeforces 543A 完全背包

編輯:關於C++

安排n個人寫m行代碼,每個人每行會出a[i]個bug,求最多出現b個bug的方案數。

一個二維的完全背包,每個人有兩個狀態:寫j行代碼出k個bug

dp[i][j][k] 前i個程序員寫錢j行出現k個bug的方案數。

dp[i][j][k] = dp[i][j-1][k-a[i]] + dp[i-1][j][k];

注意這裡數組會超內存,需要用滾動數組。

 

 

#include 
using namespace std;

int n, m, b;
long long mod;

long long a[505];

long long dp[2][505][505];

int main () {

    cin >> n >> m >> b >> mod;

    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }

    for (int i=1; i<=n; i++) dp[i % 2][0][0] = 1L;

    for (int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            for (int k=0; k<=b; k++) {
                if (k < a[i]) dp[i % 2][j][k] = dp[(i-1) % 2][j][k] % mod;
                else dp[i % 2][j][k] = (dp[i % 2][j-1][k - a[i]] + dp[(i-1) % 2][j][k]) % mod;
            }
        }
    }

    long long ans = 0;

    for (int i=0; i<=b; i++) {
        ans = (ans + dp[n % 2][m][i]) % mod;
    }

    cout << ans % mod << endl;

    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved