4.1.1 藍橋杯之動態(tài)規(guī)劃線性DP課后習(xí)題建造房屋

2024-02-02 09:11| 來源: 網(wǎng)絡(luò)整理| 查看: 265

問題描述

小藍和小橋是兩位年輕的建筑師，他們正在設(shè)計一座新的城市。

在這個城市中，有N條街道，每條街道上都有M個位置可以建造房屋(一個位置只能建造一個房屋)。建造一個房屋的費用為1元，小藍和小橋共有K元的建造預(yù)算。

現(xiàn)在，他們想知道，一共有多少種建造方案，滿足以下要求：

·在每條街道上，至少建一個房屋。

·建造的總成本不能超過K元。由于方案數(shù)可能很大，他們只需要輸出答案對10°+7取模的結(jié)果。

輸入格式

一行三個整數(shù)N,M(1≤N,M≤30)和K(1≤K≤N·

M),分別表示街道數(shù)、街道的位置數(shù)和預(yù)算。

輸出格式

一個整數(shù)，表示滿足條件的建造方案數(shù)對10?+7取模的結(jié)果。

樣例輸入

235

樣例輸出

我的答案：一、信息問題描述: 小藍和小橋需要設(shè)計城市中的房屋建造方案。條件: 城市有 N條街道。每條街道有 M個位置可建造房屋。每個位置只能建造一個房屋，建造費用為 1元。總預(yù)算為 K元。要求: 每條街道至少建一個房屋，總成本不超過K元。目標(biāo): 計算滿足條件的建造方案數(shù)，結(jié)果對 10^9 + 7 取模。輸入: N, M, K輸出: 方案數(shù) % (10^9 + 7)示例輸入: 2, 3, 5示例輸出: 8 二、分析每個信息的作用: N, M定義了問題的規(guī)模。K限制了解空間，即方案數(shù)的計算。思考和分析過程: 這是一個典型的動態(tài)規(guī)劃問題。需要考慮在預(yù)算限制下，如何在每條街道上至少建一個房屋。可以通過組合計數(shù) 來求解。三、算法設(shè)計動態(tài)規(guī)劃: 定義狀態(tài) dp[i][j] 表示在前i條街道上，使用j元預(yù)算的方案數(shù)。狀態(tài)轉(zhuǎn)移方程: dp[i][j] = sum(dp[i-1][j-k]) 其中 k 從1到 min(M, j)。四、代碼實現(xiàn)（C++） #include #include using namespace std; const int MOD = 1e9 + 7; int countBuildingPlans(int N, int M, int K) { vector dp(N + 1, vector(K + 1, 0)); dp[0][0] = 1; // 初始化 for (int i = 1; i > M >> K; cout n >> m >> k; for(int i = 0; i

【本文地址】

公司簡介

聯(lián)系我們

今日新聞

推薦新聞

專題文章