发工资咯（动态规划）

解题思路:

注意事项:

参考代码:

#include <iostream>
using namespace std;
//如果发101元，有6种情况：
//1.f(101)=f(101-1)+1
//2.f(101)=f(101-2)+1
//3.f(101)=f(101-5)+1
//4.f(101)=f(101-10)+1
//5.f(101)=f(101-50)+1
//6.f(101)=f(101-100)+1
//那么就可以得出状态转移方程为f(n)=min(f(n-1),f(n-2),f(n-5),f(n-10),f(n-50),f(n-100))+1 
//先将1到9999元所需的钱的最小张数存储在dp数组中，直接输入所发的工资，就可以求出这个程序员最少需要钱的张数 
int main(){
	int n=0;
	int dp[10000]={0};
	for(int i=1;i<10000;i++){
		int minn=0x3f3f3f3f;
		if(i>=1){
			minn=min(minn,dp[i-1]);
		}
		if(i>=2){
			minn=min(minn,dp[i-2]);
		}
		if(i>=5){
			minn=min(minn,dp[i-5]);
		}
		if(i>=10){
			minn=min(minn,dp[i-10]);
		}
		if(i>=50){
			minn=min(minn,dp[i-50]);
		}
		if(i>=100){
			minn=min(minn,dp[i-100]);
		}
		dp[i]=minn+1;
	}
	while(scanf("%d",&n)&&n!=0){
		int num=0;
		for(int i=0;i<n;i++){
			int a=0;
			scanf("%d",&a);
			num+=dp[a];
		}
		printf("%d\n",num);
	}
	return 0;
}