小哈哈

用户名：20180390139

访问量：19724

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6366
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

校门外的树（C++代码）------两种解法，复杂点的“并查集”和简单的“数组标记”
浏览：305

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：397

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：342

你可能喜欢

发工资咯-题解(C语言代码)-----------动态规划，简单求解

　　作者: 小哈哈　　　　发表时间：2019-08-18 13:33:50 浏览：377　|　评论：0　

原题链接：发工资咯

#include<stdio.h>
    #define N 10000
    #define MAX 999999
    int min(int a,int b){ return a>b ? b:a;}
    int A[7]={0,100,50,10,5,2,1};  //这是纸币的面值
    int sum=0;
    int cin(int n);  //表示如果工资为n元，那么最少需要的纸币数量为这个函数的返回值
    int main(){
    	int i=0,j,n,k,s;
    	while(scanf("%d",&k)!=EOF&&k!=0){
    		sum=0;
    		for(i=1;i<=k;i++){   
    			scanf("%d",&s);
    			sum+=cin(s);   //这里的k表示有k个人，s表示不同人的工资
    
    		}
    		printf("%d\n",sum);
    
    	}
    		return 0;
    }
    int cin(int n){   //这里才是关键的代码，动态规划
    	int i,j,dp[N]={0};   //比如dp[10]表示工资为10需要最少的纸币张数
    	for(j=1;j<=n;j++)
    		dp[j]=MAX;  //一开始让他们的值都为正无穷
    	for(i=1;i<=6;i++){
    		for(j=1;j<=n;j++){
    			if(j-A[i]>=0)  //如果工资j可以由A[i]这个面值的纸币来凑那么就走下面的路
    				dp[j]=min(dp[j],dp[j-A[i]]+1);//这是关键的状态转移方程
    			//如果要知道工资为j时的最少纸币，就看看工资为dp[j-A[i]]的最少纸币
    			//比如你的工资为55那么就看看工资为{5，40,50,53,54}这些工资需要的纸币
    			//这样dp[55]=min{dp[5],dp[40],dp[50],dp[53],dp[54]}
    			//5,40,50,53,54这些数是55分别减去50,10,5,2,1得来的
    
    		}
    	}
    
    	return dp[n];
    }

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

小哈哈

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言训练-角谷猜想（C语言代码）

发工资咯-题解(C语言代码)-----------动态规划，简单求解

评论区

精彩推荐

不容易系列（C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C语言训练-角谷猜想（C++代码）（3N+1问题）

【出圈】（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-输出九九乘法表（C++代码）

【蟠桃记】（C语言代码）

小哈哈

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言训练-角谷猜想 （C语言代码）

发工资咯-题解(C语言代码)-----------动态规划，简单求解

评论区

精彩推荐

不容易系列 （C语言代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C语言训练-角谷猜想 （C++代码）（3N+1问题）

【出圈】 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

WU-输出九九乘法表 （C++代码）

【蟠桃记】 （C语言代码）

C语言训练-角谷猜想（C语言代码）

　　评论区

不容易系列（C语言代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

【出圈】（C语言代码）

WU-输出九九乘法表（C++代码）

【蟠桃记】（C语言代码）