f433 - 165 - Stamps
題目描述
題目要求找出 K 種面額的郵票，使得使用最多 H 張郵票可以連續表示從 1 開始的最大值。輸出這些面額以及最大可表示的值。
解題思路
此題使用深度優先搜尋 (DFS) 搭配動態規劃 (DP) 來解決。首先，使用 DFS 枚舉所有可能的 K 個郵票面額組合。對於每種組合，使用 DP 計算可以表示的最大連續值。DP 陣列 dp[i] 表示是否能用給定的郵票面額表示數值 i。DP 的過程類似背包問題，嘗試用不同的郵票面額來更新 dp 陣列。在 DFS 過程中，記錄能表示的最大連續值，並在所有組合中找到最佳解。如果無法用給定的郵票面額表示從 1 到某個值的連續數列，則記錄下目前無法表示的最小值，並以此作為終止條件。
複雜度分析
- 時間複雜度: O(33^k * 101)。其中 k 是郵票種類數，33 是郵票面額的最大值，101 是 DP 陣列的大小。DFS 枚舉郵票面額組合的複雜度是 O(33^k)，DP 計算最大連續值的複雜度是 O(101)。
- 空間複雜度: O(101 + k)。DP 陣列
dp的大小是 O(101)，ansp陣列儲存最佳郵票面額組合，大小是 O(k)。
程式碼
#include <iostream>
using namespace std;
int h,k,dp[121],ansp[11],mc[11],ans;
void dfs(){
for(int i=0;i<101;++i){
dp[i]=0;
}
for(int i=0;i<101;++i){
if(i==0||dp[i]){
if(dp[i]<h){
for(int j=0;j<k;++j){
int nv=i+mc[j];
if(dp[nv]==0){
dp[nv]=dp[i]+1;
}
else{
dp[nv]=min(dp[i]+1,dp[nv]);
}
}
}
}
else if(dp[i]==0){
if(i-1>ans){
ans=i-1;
for(int j=0;j<k;++j){
ansp[j]=mc[j];
}
}
break;
}
}
return;
}
void fc(int c,int it){
if(it==k){
dfs();
return;
}
for(int i=c+1;i<33;++i){
mc[it]=i+1;
fc(i,it+1);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> h >> k){
if(h==0&&k==0)break;
ans=0;
mc[0]=1;
fc(0,1);
for(int i=0;i<k;++i){
cout << ansp[i] << " ";
}
cout << "-> " << ans << "\n";
}
}