藍橋杯算法提高VIP-郵票面值設計

題目

題目連結

題解

DFS+動态規劃。

整體思路：

第

i

個郵票的面值的範圍為：

value[i] = value[i-1]+1 ~ mx[i-1]+1

，其中

value[i]

表示第

i

個郵票的面值，

mx[i]

表示前

i

個郵票能構成的連續最大數；解釋一下這個範圍，第

i

個郵票的面值至少比第

i-1

個郵票的面值多

1

，且必須要不超過前

i-1

個郵票（預設都是最多

n

張）所能構成的最大面值

+1

，要是大于最大面值

+1

就無法滿足連續了。

是以，如果我們知道前一個郵票的面值，那麼我們就可以推出目前郵票的面值範圍，枚舉範圍内的面值，進行深搜，當找完

k

個面值的郵票時，更新一下最大連續數即可。顯然，我們現在知道第一個郵票的面值必然是

1

，是以，上述的深搜方式确實可以進行。

還有一個問題，如何确定

mx[i]

呢？

我們不去直接考慮從前

i

種郵票中選取

n

張能構成的最大面值，而是考慮前

i

種郵票構成面值為

j

的最少張數。

即使得到最小張數了，我們如何确定

mx[i]

？對于前

i

種郵票，我們隻需要從小到大周遊面值

j

，判斷枚舉到的

j

對應的最少張數是否大于

n

（

n

如題），隻要遇到了大于

n

的面值

j

，就說明無法用

n

張構成面值

j

，不滿足連續的要求，是以最多也就能構成面值為

j-1

了，我們就得到了前

i-1

種郵票選取最多

n

張所能構成的最大面值，即

j-1

。

了解了為什麼，接下來講講怎麼做。

當我們要計算

mx[i]

時，其實

value[1~i]

都已經在深搜的過程中枚舉好了，那我們将求

mx[i]

的問題再進行簡化。

求已知的若幹個數，第

i

個數的值為

a[i]

，求構成數值為

m

的數，最少需要多少個數？

比較經典的

dp

吧 ， 轉移方程為

dp[j] = min(dp[j], dp[j-a[i]]+1)

（這是一維的，降維後是這個轉移方程）

求

mx

也是一樣的，我們先通過動态規劃求出前

i

種郵票能構成面值為

j

的最少數量，之後從小到大枚舉面值，遇到所需數量大于

n

的面值就

break

，跳出時的面值

-1

即為

mx

。

如果看了上面還是沒思路，但是還想自己寫代碼的同學，可以看看下面提示的僞代碼。

本題的僞代碼：

代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 13*13;

int n, k, ans, res[N], value[N], f[N];

int dp(int x) {
	memset(f, 0x3f, sizeof f); // 動規初始化 
	f[0] = 0;
	
	for(int i = 1;i <= x;i ++)
	for(int j = value[i];j <= n*value[x];j ++) // j最大為 n*value[x]，即n張全選第x種郵票 
	f[j] = min(f[j], f[j-value[i]]+1);
	
	int i;
	for(i = 1;i <= n*value[x];i ++) if(f[i] > n) break;
	return i-1;
}

void dfs(int x, int mx) {
	if(x > k) {
		if(mx > ans) {
			ans = mx;
			for(int i = 1;i <= k;i ++) res[i] = value[i];
		}
		return ;
	}
	for(int i = value[x-1]+1;i <= mx+1;i ++) { // 枚舉第x個郵票的面值範圍 
		value[x] = i; 
		dfs(x+1, dp(x));
	}
}


int main()
{
	cin>>n>>k;
	
	dfs(1, 0); // 第一個參數是現在要确定第幾個郵票的面值，第二個參數是前面的郵票構成的最大連續數是多少 

	for(int i = 1;i <= k;i ++) cout << res[i] << ' ';
	cout << endl << "MAX=" << ans;
	return 0;
}