25分DP求助
查看原帖
25分DP求助
393811
大海中的孤帆楼主2023/8/4 11:05
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int f[110][110];
int xb[110][110];//f[i][xb[j]]
int w[110];//w[i]为第i天的最大金币数
int q(int a,int b)
{
	if(a>b)
		return a;
	return b;
}
void px(int h)
{
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n-i;++j)
		{
			if(f[h][j]<f[h][j+1])
			{
				int kkkkk=f[h][j];
				f[h][j]=f[h][j+1];
				f[h][j+1]=kkkkk;
				kkkkk=xb[i][j];
				xb[i][j]=xb[i][j+1];
				xb[i][j+1]=kkkkk;
			}
		}
	}
	return;
}
int main()
{
	cin>>t>>n>>m;
	for(int i=1;i<=t;++i)
	{
		for(int j=1;j<=n;++j)
		{
			cin>>f[i][j];
			xb[i][j]=j;
		}
	}
	w[0]=m;
	w[1]=m;
	for(int i=1;i<t;++i)//最后一天要全部卖出去,不买任何物品
	{
		px(i);//浅浅冒泡排个序
		int moneymax=0,o,oo;
		for(int j=1;j<=n;++j)
		{
			if(f[i][j]>=f[i+1][xb[i][j]])
				break;//不干不赚钱赔本生意
			o=(w[i]/f[i][j])*f[i][j];//当前花费
			oo=(w[i]/f[i][j])*f[i+1][xb[i][j]];//第二天金币
			w[i]=w[i]-o;
			moneymax=moneymax+oo;
		}
		w[i+1]=w[i]+moneymax;
	}
	cout<<w[t];
	return 0;
}
2023/8/4 11:05
加载中...