P1048 [NOIP2005 普及組] 采藥 題解

p1048 [NOIP2005 普及組] 采藥 題解

#include <iostream>
using namespace std;
int n=0,N=0,a[110]{0},b[110]{0},dp[1100]{0}; 
int main(){ 
	cin>>N;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
    for(int i=1;i<=n;i++){
		for(int j=N;j>=0;j--){
		if(j<a[i]) break;
		dp[j]=max(dp[j],dp[j-a[i]]+b[i]); 
		} 
	}
	cout<<dp[N]<<endl; 
	return 0;
} 
           

标準的動态規劃，可以背一下公式

同理 p1049

同理 p1060

同理 p1192 台階問題