分析： 典型的固定起始点的DAG最长路最短路问题。起点为S,终点为0，只是注意一些细节。
1、输出答案。 2、是否能走到0
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 100009 #define INF 0x3f3f3f3f using namespace std; int v[maxn],minv[maxn],maxv[maxn],min_coin[maxn],max_coin[maxn]; //用一个数组顺便保存字典序最小的结果。 int n; int S; void init() { minv[0] = maxv[0] =0; for(int i=1 ;i<=S ; ++i) { minv[i] = INF; maxv[i] = -INF; } } //迭代解决 int solve() { for(int i = 1 ; i<=S ; ++i) { for(int j=1 ; j<=n ; ++j) { if(i>=v[j]) { if(minv[i]>minv[i-v[j]]+1) { minv[i] = minv[i-v[j]]+1; min_coin[i] = j; } if(maxv[i]<maxv[i-v[j]]+1) { maxv[i] = maxv[i-v[j]]+1; max_coin[i] = j; } } } } } void print_ans(int *d,int s) { while(s) { printf("%d ",d[s]); s-=v[d[s]]; } } int main() { freopen("H:\\c++\\file\\stdin.txt","r",stdin); int T; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&S); for(int i=1 ; i<=n ; ++i)scanf("%d",&v[i]); init(); solve(); if(maxv[S]>0) { print_ans(max_coin,S); printf("\n"); printf("max:%d",maxv[S]); } printf("\n"); if(minv[S]<INF) { print_ans(min_coin,S); printf("\n"); printf("min:%d",minv[S]); } } return 0; }