题解 | TheCountyFair-牛客假日团队赛2I题

I-The County Fair_牛客假日团队赛2

https://ac.nowcoder.com/acm/contest/924/I

题目描述

Every year, Farmer John loves to attend the county fair. The fair has N booths $(1 \leq N\leq 400)$ , and each booth i is planning to give away a fabulous prize at a particular time $P(i) (0\leq P(i) \leq 1,000,000,000)$ during the day. Farmer John has heard about this and would like to collect as many fabulous prizes as possible to share with the cows. He would like to show up at a maximum possible number of booths at the exact times the prizes are going to be awarded.
Farmer John investigated and has determined the time $T(i,j)$ (always in range 1..1,000,000) that it takes him to walk from booth i to booth j. The county fair's unusual layout means that perhaps FJ could travel from booth i to booth j by a faster route if he were to visit intermediate booths along the way. Being a poor map reader, Farmer John never considers taking such routes -- he will only walk from booth i to booth j in the event that he can actually collect a fabulous prize at booth j, and he never visits intermediate booths along the way. Furthermore, $T(i,j)$ might not have the same value as $T(j,i)$ owing to FJ's slow walking up hills.
Farmer John starts at booth #1 at time 0. Help him collect as many fabulous prizes as possible.

输入描述:

Line 1: A single integer, N.

Lines $2..1+N$ : Line i+1 contains a single integer, $P(i)$ .

Lines $2+N..1+N+N^2$ : These $N^2$ lines each contain a single integer $T(i,j)$ for each pair (i,j) of booths. The first N of these lines respectively contain $T(1,1), T(1,2), ..., T(1,N)$ . The next N lines contain $T(2,1), T(2,2), ..., T(2,N)$ , and so on. Each $T(i,j)$ value is in the range 1...1,000,000 except for the diagonals $T(1,1), T(2,2), ..., T(N,N)$ , which have the value zero.

输出描述:

Line 1: A single integer, containing the maximum number of prizes Farmer John can acquire.

示例1

输入

4
13
9
19
3
0
10
20
3
4
0
11
2
1
15
0
12
5
5
13
0

输出

3

说明

There are 4 booths. Booth #1 is giving away a prize at time 13, booth #2 at time 9, booth #3 at time 19, and booth #4 at time 3.
Farmer John first walks to booth #4 and arrives at time 3, just in time to receive the fabulous prize there. He them walks to booth 2 (always walking directly, never using intermediate booths!) and arrives at time 8, so after waiting 1 unit of time he receives the fabulous prize there. Finally, he walks back to booth #1, arrives at time 13, and collects his third fabulous prize.

解答

题目大意：有一些村庄，各个村庄间有一些长短不一的道路，每个村庄都有一个办法奖励的时间Pi。一个人从村庄1开始游历。但是有一个特殊的规则：他每到达一个村庄，都必须在那里获得一个奖励，否则他不肯动身去这个村庄（这个条件太坑爹啊）。

算法：
就是个普通的生成类DP，初始化很重要
因为只有从村庄1出发是不一定要等到时间P1的，从其它村庄出发都必须等到时间Pi拿到奖励才走
（题面中规定“：he will only walk from booth i to booth j in the event that he can actually collect a fabulous prize at booth j.）
所以对于任何 $w(1,i)<Pi$ 的城市 $d[i]=1,$ 否则 $d[i]=0;$
然后按照 $Pi$ 排序，因为从任何一个村庄（除了村庄1）肯定是不可能走到 $Pi$ 比它早的村庄去的（因为去了之后等到地老天荒也拿不到奖励。。）
然后对于任何 $Pi+w(i,j)<=Pj$ 的 $i$ 和 $j$ ， $d[j]=max(d[i]+1,d[j])$ 。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
 
typedef struct
{
int a,b;
}node;
 
bool cmp(const node& x,const node& y)
{
return x.a<y.a;
}
 
int d[450],cap[450][450];
node p[450];
 
int main()
{
int n,i,j,k,ans;
while(scanf("%d",&n)==1)
{
memset(d,-INF,sizeof(d));
ans=0;
for(i=1;i<=n;i++)
{
p[i].b=i;
scanf("%d",&p[i].a);
}
sort(p+1,p+1+n,cmp);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cap[i][j]);
for(k=1;p[k].b!=1;k++);
for(i=1;i<=n;i++)
if(cap[p[k].b][p[i].b]<=p[i].a)
d[i]=1;
for(i=1;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(p[j].a+cap[p[j].b][p[i].b]<=p[i].a)d[i]=d[i]>d[j]+1?d[i]:d[j]+1;
}
ans=ans>d[i]?ans:d[i];
}
printf("%d\n",ans);
}
}

来源：frog1902