首页 > 代码库 > Uva 147-Dollars(DP)
Uva 147-Dollars(DP)
题目链接:点击打开链接
换硬币问题。不过存在分,所以是小数输入,一开始因为精度问题wa一发。而且。。计数用long long。。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair<int,int> #define ull unsigned long long using namespace std; int v[]={10000,5000,2000,1000,500,200,100,50,20,10,5}; ll dp[30010]; double n; void solve() { memset(dp,0,sizeof(dp));dp[0]=1; int m=(int)(n*100+0.5); for(int i=0;i<11;i++) for(int j=v[i];j<=m;j++) dp[j]+=dp[j-v[i]]; printf("%6.2lf%17lld\n",n,dp[m]); } int main() { while(~scanf("%lf",&n)&&n) solve(); return 0; }
Uva 357 :点击打开链接
同样的找零钱问题,贴个打表过的。
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1005 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1<<40+10 #define pp pair<int,int> #define ull unsigned long long using namespace std; int v[]={1,5,10,25,50}; ll dp[30002];int n; void init() { memset(dp,0,sizeof(dp));dp[0]=1; for(int i=0;i<5;i++) for(int j=v[i];j<=30000;j++) dp[j]+=dp[j-v[i]]; } int main() { init(); while(~scanf("%d",&n)) { if(dp[n]!=1) printf("There are %lld ways to produce %d cents change.\n",dp[n],n); else printf("There is only 1 way to produce %d cents change.\n",n); } return 0; }
Uva 147-Dollars(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。