---
# System prepended metadata

title: d637 路過的鴨duck

---

# d637 路過的鴨duck
## [題目連結](https://zerojudge.tw/ShowProblem?problemid=d637)
## 解題想法
* 和另一題方法相同，用動態規劃解
## 遭遇到的困難
* 由於在另一題已嘗試過此寫法，故只有熟練此方法
## 程式碼
```cpp=01
#include<stdio.h>
#include<vector>
using namespace std;
int main(){
	int n,a,b,i,j;
	scanf("%d",&n);
	vector<int> feed[n+1];
	feed[0].reserve(101);
	for(i=0;i<=100;i++)feed[0][i]=0;
	for(i=1;i<=n;i++){
		feed[i].reserve(101);
		feed[i][0]=0;
		scanf("%d%d",&a,&b);
		for(j=1;j<=100;j++){
			if(j<a)feed[i][j]=feed[i-1][j];
			else{
				if((b+feed[i-1][j-a])<feed[i-1][j])feed[i][j]=feed[i-1][j];
				else feed[i][j]=b+feed[i-1][j-a];
			}
		}
	}
	printf("%d",feed[n][100]);
	return 0;
} 