题解 P5020 【货币系统】

直接导致我退役的水题，介绍一下我考场上的奇怪思路。 看到题意，直接想到了ISIJ 2018的“[很多序列](https://blog.csdn.net/jpwang8/article/details/82660425)”一题，打了个最短路上去。思路是先将所有数从小到大排序。建立$a_1$个点（$a_1$为最小的面值），点$x$代表模$a_1$余$x$的所有数。对每个点$x$，从$x$到$x+a_i$连一条长为$a_i$的边。跑完最短路后，我们得到的距离$dis[x]$，就是模$a_1$余$x$的能组成的最小金额。 两种货币系统等价，当且仅当两种货币系统的$dis$数组完全相同。我们可以记录一个```trans```数组，表示转移时使用了哪种币值。要注意的是，当一种金额有多种转移路径时，应选择最小的转移。只需在松弛操作时顺便修改即可。 其实这种做法的本质就是对大背包的一种优化，但是考场上忘记了问题的本质，没有用最简单的方法解决。最后还忘清空了```trans```数组（由于样例很水，竟然过了大样例），导致自己Day1还没Day2高。 ``` #include<cstdio> #include<cstring> #include<algorithm> #include<utility> #include<queue> #include<set> #include<vector> #define LL long long #define PLI std::pair<LL,int> int val[25005]; LL dist[25005]; bool vis[25005]; int trans[25005]; int Dijkstra(int n)//Dijkstra跑背包 { int MOD=val[1];//模a1意义下 memset(dist,0x3f,sizeof(dist)); memset(vis,0,sizeof(vis)); memset(trans,0,sizeof(trans));//考场上少了这一行，当场GG dist[0]=0; std::priority_queue<PLI,std::vector<PLI>,std::greater<PLI> > Q; Q.push(PLI(0,0)); int vised=0; while(vised!=MOD&&!Q.empty()) { int u=Q.top().second; Q.pop(); if(!vis[u]) { vis[u]=true; ++vised; for(int i=2;i<=n;++i) { int v=(u+val[i])%MOD; if(dist[v]>dist[u]+val[i])//松弛，一定修改转移 { dist[v]=dist[u]+val[i]; trans[v]=val[i]; Q.push(PLI(dist[v],v)); } else if(dist[v]==dist[u]+val[i]&&val[i]<trans[v])//有更优的转移 { trans[v]=val[i]; } } } } std::set<int> s;//找一下有多少种转移（含0） for(int i=0;i<MOD;++i) { s.insert(trans[i]); } return s.size(); } int main() { int t; scanf("%d",&t); int n; while(t--) { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&val[i]); } std::sort(val+1,val+n+1);//排序，从小到大枚举转移 printf("%d\n",Dijkstra(n)); } return 0; } ```