LevOJ P1291 西蒙斯的金钱帝国

题目描述

詹姆斯・西蒙斯是世界级的数学家，也是最伟大的对冲基金经理之一。全球收入最高的对冲基金经理，年净赚 15 亿美元。在华尔街，韬光养晦是优秀的对冲基金经理恪守的准则，詹姆斯？西蒙斯也是如此，即使是华尔街专业人士，对他及其旗下的文艺复兴科技公司也所知甚少。然而在数学界，西蒙斯却是大名鼎鼎。早在上个世纪，詹姆斯？西蒙斯就是一位赫赫有名的数学大师。在 2007 年 “华尔街最会赚钱的基金经理” 排行榜中，这位 70 岁的数学大师以年收入 13 亿美元，位列第五。

西蒙斯留下的是关于金钱的问题。想象一下，如果一个国家只有 3 块、6 块或者 10 块三种货币，你就不可能付清 1、2、4、5、7、8、11、14 或者 17 块钱，显然这样的金融系统将会崩溃。给出 N 种货币计算出不能用这 n 种货币表示的最大面值数目（每种货币数量无限），数据保证一定有解。

输入

第一行一个整数 n，表示货币的数目。

接下来 n 行表示 n 种不同的货币。

输出

输出一行，表示不能用这 n 种货币表示的最大面值数目

样例输入

3

3 6 10

样例输出

17

题解

        这题实际上是一种特殊的最短路问题，叫做同余最短路。

        限于我目前对它的理解还不够深刻，暂时还说不出个所以然。具体的讲解可以点击 这里 

也可有参考 OI Wiki 里面的介绍：https://oi-wiki.org/graph/mod-shortest-path/。

        下面是此题的AC代码：

#include 
#include 
#include 
#include  using namespace std;int n, price[100005];	//初始数据 
//u: 起始结点  v:终止结点  w：边权 
int u[100005], v[100005], w[100005], tot;	
//邻接表 
int first[100005], nxt[100005];
//距离 
int dis[100005];int main(){while(scanf("%d", &n) != EOF){tot = 0;//读取数据 for(int i = 0; i < n; ++i){scanf("%d", price+i);if(price[i] < price[0])	swap(price[i], price[0]);}//建图 int tmp = price[0];memset(first, -1, sizeof first);for(int i = 0; i < n; ++i){for(int j = 0; j < tmp; ++j){u[++tot] = j, v[tot] = (j + price[i]) % tmp, w[tot] = price[i];nxt[tot] = first[j], first[j] = tot;}}//SPFA求最短路 memset(dis, 0x3f, sizeof dis);dis[0] = 0;bool inq[100005] = {0};queue q;q.push(0);	inq[0] = 1;while(!q.empty()){int fq = q.front();q.pop(), inq[fq] = 0;for(int i = first[fq]; ~i; i = nxt[i]){if(dis[v[i]] > dis[u[i]] + w[i]){dis[v[i]] =	dis[u[i]] + w[i];if(!inq[v[i]])	q.push(v[i]), inq[v[i]] = 1;}}}//打印结果 int res = -1;for(int i = 0; i < tmp; ++i)	res = max(res, dis[i]);printf("%d\n", res - price[0]);}return 0;
} 

总结

        不得不说，这题刷新了我对最短路的认知。感觉比较遗憾的是，没能用自己的语言把同余最短路的精髓描述出来，如果后面有机会，应该把它补上。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！