thinking:
数字三角形：就是设定一个数组，来记录每一行选的是其下一行的哪一个边可以按路径输出了。
找钱问题：最少张，从小面额开始找，如果遇到一个张面额可以整mod或者此时钱总和-该面额存在，那么取这个面额，DP思想。
数字三角形代码：
#include <bits/stdc++.h> #define MAXN 999 int map1[MAXN][MAXN]; int map2[MAXN][MAXN]; int map3[MAXN][MAXN]; int walk1[MAXN][MAXN]; int walk2[MAXN][MAXN]; int main(){ int n,m,i,j,k,t1,t2,f1,f2; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=i;j++){ scanf("%d",&t1); map1[i][j]=t1; map2[i][j]=t1; map3[i][j]=t1; } /*for(i=1;i<=n;i++){ //此处用来判断输入的图形长什么样 for(j=1;j<=i;j++) printf("%d ",map1[i][j]); cout << endl;}*/ for(i=n-1;i>=1;i--){ for(j=1;j<=i;j++){ if(map1[i+1][j]>map1[i+1][j+1]){ //walk1用来记录最小走过的路径 map1[i][j]=map1[i+1][j+1]+map1[i][j]; walk1[i][j]=j+1; }else{ map1[i][j]=map1[i+1][j]+map1[i][j]; walk1[i][j]=j; } if(map2[i+1][j]>map2[i+1][j+1]){ //walk2用来记录最大走过的路径 map2[i][j]=map2[i+1][j]+map2[i][j]; walk2[i][j]=j; }else{ map2[i][j]=map2[i+1][j+1]+map2[i][j]; walk2[i][j]=j+1; } } } j=1; for(i=1;i<=n;i++){ if(i!=n) printf("%d->",map3[i][j]); else printf("%d",map3[i][j]); j=walk1[i][j]; } printf("\n"); printf("最短路径为%d\n",map1[1][1]); j=1; for(i=1;i<=n;i++){ if(i!=n) printf("%d->",map3[i][j]); else printf("%d",map3[i][j]); j=walk2[i][j]; } printf("\n"); printf("最长路径为%d\n",map2[1][1]); return 0; } /*输入样例为: 8 //这个8表示有8行数字 12 15 16 6 8 5 10 8 16 11 18 7 16 15 17 4 14 3 15 23 3 24 17 20 9 4 16 21 9 18 2 15 7 7 8 6 */ 找钱问题： #include<bits/stdc++.h> #define MAXN 999 using namespace std; int a[MAXN]; int a1[MAXN][MAXN]; int a2[MAXN][MAXN]; int qq1[MAXN]; int qq2[MAXN]; int main(){ int n,sum,i,j,k,t1,t2,s; memset(qq1,0,sizeof(qq1)); memset(qq2,0,sizeof(qq2)); memset(a1,0,sizeof(a1)); memset(a2,0,sizeof(a2)); scanf("%d%d",&n,&sum); for(i=0;i<n;i++) scanf("%d",a+i); sort(a,a+n); for(i=0;i<n;i++){ //最少需要张数动态规划计算 for(j=1;j<=sum;j++){ if(j%a[i]==0){ memset(a1[j],0,sizeof(a1[j])); a1[j][i]=j/a[i]; qq1[j]=j/a[i]; } else if(j-a[i]>0&&qq1[j-a[i]]){ qq1[j]=qq1[j-a[i]]+1; for(k=0;k<n;k++) a1[j][k]=a1[j-a[i]][k]; a1[j][i]++; } } } for(i=n-1;i>=0;i--){ //最多需要张数动态规划计算 for(j=1;j<=sum;j++){ if(j%a[i]==0){ memset(a2[j],0,sizeof(a2[j])); a2[j][i]=j/a[i]; qq2[j]=j/a[i]; } else if(j-a[i]>0&&qq2[j-a[i]]){ qq2[j]=qq2[j-a[i]]+1; for(k=0;k<n;k++) a2[j][k]=a2[j-a[i]][k]; a2[j][i]++; } } } printf("%d元最少一共需要%d张\n",sum,qq1[sum]); for(i=0;i<n;i++) printf("使用%d元%d张\n",a[i],a1[sum][i]); printf("\n"); printf("%d元最少一共需要%d张\n",sum,qq2[sum]); for(i=0;i<n;i++) printf("使用%d元%d张\n",a[i],a2[sum][i]); return 0; } /*输入样例： 4 100 //第一个数字意思是有4种面额的硬币 第二个数字意思是面值之和 3 5 7 14 //下一行的4个数字为给定的面额 */
