【CSP-J 2019】纪念品

题目简要

小伟突然获得一种超能力，他知道未来T天N种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量，以及卖出一个该纪念品换回的金币数量。

每天，小伟可以进行以下两种交易无限次：

1．任选一个纪念品，若手上有足够金币，以当日价格购买该纪念品；

2．卖出持有的任意一个纪念品，以当日价格换回金币。 每天卖出纪念品换回的金币可以立即用于购买纪念品，当日购买的纪念品也可以当日卖出换回金币。当然，一直持有纪念品也是可以的。

T 天之后，小伟的超能力消失。因此他一定会在第 T 天卖出所有纪念品换回金币。 小伟现在有 M    枚金币，他想要在超能力消失后拥有尽可能多的金币。

输入格式、样例

输入文件名为 souvenir.in。 第一行包含三个正整数 T, N, M，相邻两数之间以一个空格分开，分别代表未来天数 T，纪念品数量 N，小伟现在拥有的金币数量M。 接下来T行，每行包含 N 个正整数，相邻两数之间以一个空格分隔。第i行的N 个正整数分别为 Pi,1, Pi,2, … … , Pi,

6 1 100 50 20 25 20 25 50

输出格式、样例

输出文件名为 souvenir.out。 输出仅一行，包含一个正整数，表示小伟在超能力消失后最多能拥有的金币数量。305

其他

【输入输出样例 1 说明】 最佳策略是： 第二天花光所有 100 枚金币买入 5 个纪念品 1； 第三天卖出 5 个纪念品 1，获得金币 125 枚； 第四天买入 6 个纪念品 1，剩余 5 枚金币； 第六天必须卖出所有纪念品换回 300 枚金币，第四天剩余 5 枚金币,共 305 枚金币。 超能力消失后，小伟最多拥有 305 枚金币。

【数据规模与约定】 对于 10% 的数据，T=1。 对于 30% 的数据，T≤4,N≤4,M≤100，所有价格 10≤Pi,j​≤100。 另有 15% 的数据，T≤100,N=1。 另有15% 的数据，T=2,N≤100。 对于 100% 的数据，T≤100,N≤100,M≤103，所有价格1≤Pi,j​≤104，数据保证任意时刻，小明手上的金币数不可能超过 10^4。

分析

dp完全背包。

#include<bits/stdc++.h>
using namespace std;
long long t,n,m;//未来天数 T，纪念品数量 N，小伟现在拥有的金币数量M。
long long a[110][1010];//第i天第j件价格
long long f[10010];
int main()
{
	cin>>t>>n>>m;
	for(int i=1;i<=t;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];//输入
		}
	}
	int ans=m;//一开始没买，可认为盈利m元。
	for(int T=2;T<=t;T++)//从第二天开始买。
	{
		memset(f,-0x7f,8*10010);//设置f全为-0x7f.
		f[0]=0;//0元换来0元的盈利。
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=ans;j++)//f[j]:j元获得的最大利润。so，枚举从0到ans（拥有的钱）
			{
				if(f[j]!=-0x7f7f7f7f)//可转移
				{
					f[j+a[T-1][i]]=max(f[j+a[T-1][i]],f[j]+a[T][i]-a[T-1][i]);
                                        //f[j+a[T-1][i]]：“超能力”相当于第T天可用第T-1天的money买东西，所以此意为：花费j+昨天价格的这样东西获得最大利润。f[j]+a[T][i]-a[T-1][i]：j元+今天价-昨天价（利润）获得的最大利润。
				}
			}
		}
		long long we=0;
		for(int k=1;k<=ans;k++)
		{
			we=max(we,f[k]);//打一次擂台，比较最值。
		}
		ans+=we;
	}
	cout<<ans;//结束！
	return 0;
}

C++：邻接矩阵存图

给定n个点, m条单向边  n<=1000, m <= 100000

有k个询问，询问x出去的所有边及其权值，如果有多条边，终点编号小的先输出，具体见样例

输入格式(Format Input)

第一行输入两个整数n和m，表示有n个点和m条边。 接下来输入m行，每行三个整数x y z，表示x到y有一条权值为z的单向边。如果两个点之间有多条边，保留权值最小的一条。 输入一个数字k，表示有k个询问（k<=n）。 接下来输入k行，每行输入一个整数x（x表示节点编号）。

输出格式(Format Output)

对于每一个询问x，输入与x相连的边，每条边占一行，对于每条边先输出终点编号，再输出边权，中间用空格隔开。

输入样例(Sample Input) 

4 5

1 2 5

1 3 4

2 4 3

1 4 8 1 3 3

2

2

输出样例(Sample Output)

2 5 3 3 4 8 4 3

前项星写法：

#include<bits/stdc++.h>
using namespace std;
int n,m,k,cnt=0;//cnt表示第i条边，默认为0。 k:几组查询 
int last[1010];//last[i]代表i后的第一个边。
int nxt[1010];//nxt[i]代表第i条边的下一条边。
int w[1010];//w[i]代表第i条边的权值。
int ed[1010];//ed[i]表示第i条边的“终点”。
void edge(int x,int y,int z)//新增一条从x至y，边权为z的边。
{
	cnt++;//此乃第i条边！
	ed[cnt]=y,w[cnt]=z;//i条边终点为y,边权为z。
	//前插法 将数据从“头 ”插入 。 
	nxt[cnt]=last[x];//i的下一条边为第x（起点）点后的第一条边。 
	last[x]=cnt;//x（起点）点后的第一条边为第i条边。 
	//注意！先让i的下一条边为第x（起点）点后的第一条边，再让x（起点）点后的第一条边为第i条边。这样才不会将图“断掉 ”。 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		edge(x,y,z);//新增一条从x至y，边权为z的边。 
	}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int x;
		cin>>x;//键入要查询的节点。 
		for(int j=last[x];j;j=nxt[j])	//设j为 x后的第一条边。如果j!=0，就一直运行。这遍循环后，j来到j+1条边。 
		{
			cout<<ed[j]<<" "<<w[j]<<endl;	//输出终点与边权。 
		}
	}
	return 0;
}

但由于本人太菜了😭，只会前插法，所以还是用暴力点的法子吧。这法子存储的是点，上边的是边。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int g[1001][1001];
int main()
{
	cin>>n>>m;
	memset(g,-1,sizeof(g));//初始值全列为-1，由于本体无负权边，so，无伤大雅。
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		if(g[x][y]==-1) g[x][y]=z;//如果直接min，g[x][y]永远为-1，so，特判一下。
		else g[x][y]=min(g[x][y],z);
	}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int x;
		cin>>x;
		for(int j=1;j<=n;j++)//快乐地循环n次。
		{
			if(g[x][j]!=-1)//有边权！！！
			{
				cout<<j<<" "<<g[x][j]<<endl;//快乐地输出
			}
		}
	}
	return 0;
}

感性与希望——读《流浪地球》有所感

宇宙，无边无沿，浩瀚无垠。仰望苍穹，满天星斗，一轮明月，皓照夜空，那些点点繁星连成一条银链，在夜空中流动。我们在宇宙中仅为沧海一粟。地球，如一条小舟，在跌宕起伏的大海上。它随时都会倾翻。人类，该如何应对，宇宙出的一道道难题？

《流浪地球》给我们提出了答案——希望。

“希望，是像钻石一样珍贵的东西。”是的，希望如钻石五彩斑斓，多姿多彩。在茫茫宇宙中，人类与地球没有退缩与逃避之机，没有救援，只有希望，支持着人类平视前方，迈下沉重的一步，又一步。

因为希望，人类可以不惜一切的代价，在地球表面屹立起一万多座高大的“行星发动机”，开启长达两千五百年，一百代人的流浪之旅；因为希望，人类心中的责任感油然而生。他们用自己的生命换取人类文明的延续，点燃、照亮一切光明与黑暗。他们可能默默无闻，可能并不会留名千史，但，永不屈服！英雄坦然面对一切灾难，乃至死亡。尸骨无处安放，但这并不能磨灭人类的勇气，勇气是人类最伟大的赞歌！

因为希望，即使有地球叛军的阻拦与抗拒，那最后的五千名地球派为防止发动机失控，保护地球的安全，没有反抗，在冰川之上英勇赴死。在叛军欢呼时，太阳氦闪爆发，恰恰证明了，他们的选择是正确的！

书中说，让人类保持理智是一种奢求。但何时，人类是理智的呢？人类之所以伟大，是因为拥有情感。理性可以更为客观、正确地处理事情，但人类最终的选择，都是出于感性的。感性创造了希望，希望创造了无限可能。例如抗美援朝战争，没有保家卫国、誓死抗敌的豪情壮志，我们无法取胜。没有希望就没有英雄，没有情感就没有人类。情感赋予了我们灵魂，希望赋予了我们光明！

不知时间会将人类文明推向何处，不知地球是否能跨过两千五百年，一百代人的漫长旅途，但人类的勇气与希望，将永刻于漫漫星空之下。这浩渺莫测的星空，就是人类永恒的纪念碑！祝地球，好运！