[XIN算法应用]NOI2020美食家

XIN(\(updated 2021.6.4\))

对于很多很多的题目，发现自己并不会之后，往往会直接冲上一个XIN队算法，然而，这样 \(\huge{\text{鲁莽}}\) 的行为只能获得 TLE，所以，我们要考虑如何拿到最大的部分分值。

noi 2020 美食家

题目

看完题目之后，发现这个题目的范围很鬼畜，似乎只能用 \(\mathcal O(log_2T)\) 的复杂的过去。。。。

之后大脑空白 \(1e9\) 分钟。。。。。。。。。。。。。。。。。

之后目光转向 1 ~ 8 的测试点，发现似乎可以用 \(\mathcal O(nT)\) 的复杂度拿到，所以开始考虑部分分数。

如果使用以往的XIN队算法，那么预测应该最多只拿到 4 个测试点，所以我们就要考虑非纯暴力解法

首先我们要推出方程：怎么推呢，用 \(\huge{\text{杠哥大定理}}\)。

所以方程就是:

\[f_{pos,time}=\max\limits_{link_{pos,to}}f_{to,time-edge[i].w} + c_i
\]

之后就可以使用 \(\huge{\text{记忆化}}\)来解决

	int xin_team(int x,int tim)

	{

		if(f[x][tim]) return f[x][tim];

		if(x == 1 and !tim)

			{ok = true;return c[x];}

		else if(tim < 0)

			return 0x7f7f7f7f7f7f7f7f;

		int maxx = -0x7f7f7f7f7f7f7f7f;

		for(register int i=0;i<link[x].size();++i)

		{

			register int y = link[x][i].pos;

			int zhuan = xin_team(y,tim - link[x][i].val);

			if(zhuan < 0x7f7f7f7f7f7f7f7f)

				maxx = max(maxx,zhuan);

		}

		for(register int i=1;i<=k;++i)

			if(x == a[i].x and tim == a[i].t)

				{f[x][tim] += a[i].y;break;}

		f[x][tim] += maxx + c[x];

//		cout<<"x = "<<x<<" time = "<<tim<<endl;

		return f[x][tim];

	}

这就是 核心代码

复杂度 \(\mathcal O(nT)\) 还算比较 \(\color{red}{\text{优秀}}\)

之后就可以拿到 \(40pts\) 了！

记录

\(code_{tot}:\)

#include<cmath>

#include<queue>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define int long long

#define m(c,num) memset(c,num,sizeof c)

#define INF 0x7f7f7f7f

#define debug cout<<"debug"<<endl

#define freopen eat = freopen

#define scanf a14 = scanf

namespace xin_io

{

	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++

	char buf[1<<20],*p1 = buf,*p2 = buf; FILE *eat; int a14;

	inline void openfile() {freopen("t.txt","r",stdin);}

	inline void outfile()  {freopen("o.txt","w",stdout);}

	inline int get()

	{

		int s = 0,f = 1;register char ch = gc();

		while(!isdigit(ch))

		{if(ch == '-') f = -1;ch = gc();}

		while(isdigit(ch))

		{s = s * 10 + ch - '0';	ch = gc();}

		return  s * f;

	}

}

static const int maxn = 201,maxt = 52502;

using namespace xin_io;

namespace xin

{

	class xin_edge{public:int w,next,ver;}edge[maxn];

	class xin_data{public:int pos,val;xin_data(int x,int y):pos(x),val(y){}};

	class xin_food{public:int t,x,y;}a[maxn<<2];

	int head[maxn],zhi = 0;

	inline void add(int x,int y,int z)

	{edge[++zhi].ver = y;edge[zhi].w = z;edge[zhi].next = head[x]; head[x] = zhi;}

	int c[maxn];

	int n,m,t,k;

	bool ok = false;

	vector <xin_data> link[maxn];

	int f[maxn][maxt];

	int xin_team(int x,int tim)

	{

		if(f[x][tim]) return f[x][tim];

		if(x == 1 and !tim)

			{ok = true;return c[x];}

		else if(tim < 0)

			return 0x7f7f7f7f7f7f7f7f;

		int maxx = -0x7f7f7f7f7f7f7f7f;

		for(register int i=0;i<link[x].size();++i)

		{

			register int y = link[x][i].pos;

			int zhuan = xin_team(y,tim - link[x][i].val);

			if(zhuan < 0x7f7f7f7f7f7f7f7f)

				maxx = max(maxx,zhuan);

		}

		for(register int i=1;i<=k;++i)

			if(x == a[i].x and tim == a[i].t)

				{f[x][tim] += a[i].y;break;}

		f[x][tim] += maxx + c[x];

//		cout<<"x = "<<x<<" time = "<<tim<<endl;

		return f[x][tim];

	}

	inline short main()

	{

	#ifndef ONLINE_JUDGE

		openfile();

	#endif

		n = get(); m = get(); t = get(); k = get();

//		memset(f,128,sizeof(f));

		if(t > 52501) {cout<<-1<<endl;return 0;}

		for(register int i=1;i<=n;++i) c[i] = get();

		for(register int i=1;i<=m;++i)

		{register int x = get(),y = get(),z = get();add(x,y,z),link[y].push_back(xin_data(x,z));}

		for(register int i=1;i<=k;++i) a[i].t = get(),a[i].x = get(),a[i].y = get();

		int ans = xin_team(1,t);

		if(ok)

			cout<<ans<<endl;

		else

			cout<<-1<<endl;

		return 0;

	}

}

signed main() {return xin::main();}

巴特西

[XIN算法应用]NOI2020美食家

XIN(\(updated 2021.6.4\))

noi 2020 美食家

最新文章

热门文章