题解：P1048 [NOIP2005 普及组] 采药

思路

经典 01背包问题。观察到题目中含有「时间」与「价值」字样，考虑使用背包求解。

定义

w_i

表示采药时间，

c_i

表示药的价值和数组

f_{i,v}

，表示采前

i

株草药花费

v

个单位时间获得的最大价值。显见，对于前

i

株草药，可以选择采与不采第

i

株草药，采后会花费

w_i

的时间。根据上文，我们可以列出转移方程：

f_{i,v} \gets \max(f_{i-1,v},f_{i-1,v-w_i} + c_i)

其中，

f_{i-1,v}

表示不采这株草药的价值，

f_{i-1,v-w_i} + c_i

表示采这株草药的价值，我们要取二者最大值。

显见最后输出结果为

f_{M,T}

。

时间复杂度为

O(TM)

。

实现

CPP

# include <iostream>
using namespace std;
int w[1145],c[1145],f[1145][1145];
int main(){
	int n,m; cin >> m >> n;
	for (int i = 1;i <= n;i++) cin >> w[i] >> c[i];
	for (int i = 1;i <= n;i++){
		for (int v = m;v > 0;v--){
			if (w[i] <= v) f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
			else f[i][v] = f[i-1][v];
		}
	}cout << f[n][m];
	return 0;
}

题解：P1048 [NOIP2005 普及组] 采药

文章操作

思路

实现

相关推荐

评论

题解：P1048 [NOIP2005 普及组] 采药