中国招标机构哪个网站做的好,游戏怎么开发,企业做网站应注意什么,tag 网站托管公司##题目#xff1a; 有n种硬币#xff0c;面值分别为v1, v2, …, vn#xff0c;每种都有无限多。给定非负整数S#xff0c;可以选用多少个硬币#xff0c;使得面值之和恰好为S#xff1f;输出硬币数目的最小值和最大值。
Input 第一行两个整数#xff0c;n#xff0c;S…##题目 有n种硬币面值分别为v1, v2, …, vn每种都有无限多。给定非负整数S可以选用多少个硬币使得面值之和恰好为S输出硬币数目的最小值和最大值。
Input 第一行两个整数nS1≤n≤100 0≤S≤100000。 第二行n个整数vi-1…n(1≤vi≤S)。
Output 第一行两个整数分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。 第二行 a 个整数分别表示使用的是第几种硬币。 第三行 b 个整数分别表示使用的是第几种硬币。
Sample Input 6 12 1 2 3 4 5 6
Sample Output 2 12 6 6 1 1 1 1 1 1 1 1 1 1 1 1
##分析与解
假如s是12怎么弄个金钱加加减减就到十二呢 假设每个结点表示剩的钱数 怎么和DAG想到一块可以这么想现在已知一个路的起点s和终点0每多加一个钱s就变到另一个数s2现在找s2和终点0的路这样就成了一个DAG
##思考 我们用递推想找剩下s元到剩下零元的最小使用钱的次数 现在找最短路径的话 递推公式dmin[i]min(dmin[i],dmin[i-v[j]]1) 我们初始化dmin[0]0剩下零元到零元不需要钱次数为零 dmin[i]的话就是看dmin[i]到零元的最小使用钱次数他需要和dmin[i-v[j]]1比较其中1是说dmin[i-v[j]]加上v[j],使用了dmin[i-v[j]]加上一次使用v[j]的次数 我们可以发现dmin[s]可以由dmin[0]向上推出
那不妨把递推公式转换成迭代
如果剩下的钱i减去v[j]大于零说明可以通过dmin[i-v[j]]1来确定dmin[i] 那么假设我们的dmin[i]就等于dmin[i-v[j]]1并且dmin[0]等于0所以这样一步一步推出dmin[s]
由于题目说字典序我们再写最大最小值时候也是遇见大于max的就存标号更改max后面来个等于max的我们不能再存标号因为我们要的是第一个数所以后面来的必须要大于max我们才改标号
这个也是一样的道理必须有新的dmin[i-v[j]]1比之前的dmin[i-v[j2]]1小的时候我们替换掉dmin[i]的值。 由于要考虑输出输出的都是v[j],那我们就要记录每一个i他减的v[j]是什么就是当dmin[i]dmin[i-v[j]]1时我们不仅替换dmin[i]dmin[i-v[j]]1,还要替换path_min[i]j,path_min[i-v[j]]j2,如果i-v[j]0,此时说明v[j]v[j2]s 我这输出没排序如果要排序的话存到数组里然后输出
int V[maxN];i是第几种v[i]是第i种的价值 int Dmin[maxS];dmin[i]是i到0所需的最小路径 int Dmax[maxS]; int path_min[maxS];path_min[i]是最小路径中由i走到下一个结点所减去的那个数v[j]的下标j int path_max[maxS];
#includeiostream
#includecstdio
#includecstdlib
#includecstring
#includealgorithm
using namespace std;const int maxN200;
const int maxS200000;
const int inf2000000000;
int n,S;
int V[maxN];
int Dmin[maxS];
int Dmax[maxS];
int path_min[maxS];
int path_max[maxS];void print_ans(int *d,int s){while(s){printf(%d ,d[s]);s-V[d[s]];}
}int main()
{cinnS;for (int i1;in;i){cinV[i];}for (int i1;iS;i){Dmin[i]inf;Dmax[i]-inf;}Dmin[0]0;Dmax[0]0;for (int i1;iS;i){for (int j1;jn;j)if (iV[j]){if (Dmin[i]Dmin[i-V[j]]1)//1走的v【j】 {Dmin[i]Dmin[i-V[j]]1;path_min[i]j;}if (Dmax[i]Dmax[i-V[j]]1){Dmax[i]Dmax[i-V[j]]1;path_max[i]j;}}}coutDmin[S] Dmax[S]endl;print_ans(path_min,S);printf(\n);print_ans(path_max,S);printf(\n);return 0;
}
