题解 P6759 【[USACO2006 OPEN] 县集市 The County Fair】

· · 题解

思路：

这道题目我们可以用动态规划做。我们先对时间顺序排序，时间小的在前面，因为只有先经过小的时间才可以推算大的时间。接着我们就有了一个数组，用来记录在前 i 个礼物中最多能拿几个礼物，且第 i 个礼物一定要取。当然这个要经过前面的推算才能得出。

方程：

我们需要通过前面的时间推算那么我们就可以做一个判断：如果前面那个礼物发放的时间加上那个集市到这个集市的时间小于等于这个礼物发放的时间，那么就可以从那个集市过来，之所以是要一定小于等于，是因为这个礼物必须要取。通过所有可以到达的集市，更新数组的最大值。

if(t[s[j].b][s[i].b]+s[j].t<=s[i].t)
    dp[i]=max(dp[j]+1,dp[i]);

注意：

注意上面的记录走两个摊位的路需要的时间的数组里的变量不要写反，因为这条路来回的时间不一定相同，我们要严格遵循状态化转移方程，而且 dp_n 不一定是最大的答案，所以我们需要一个变量来更新最大值。

代码:

由于变量名比较土，所以注释就比较多了。

#include <bits/stdc++.h>
using namespace std;
struct o//每一个集市的信息，下面的t和b分别是发放礼物的时间和集市的编号，记录编号是因为下面的排序有可能打乱编号
{
    int t;
    int b;
};
int p(o o1,o o2)//定义排序的优先级，发放礼物时间前的集市在前面
{
    return o1.t<o2.t;
}
int dp[401],ans;//把它们放在外面，自动清零
int main()
{
    o s[401];//定义所有的集市
    int n,t[401][401];//集市数量和走这两个集市的路的时间
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i].t);
        s[i].b=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&t[i][j]);
    sort(s+1,s+n+1,p);
    s[0].b=1,s[0].t=0;//赋初始值，在第0分钟，FJ在第一个集市
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(t[s[j].b][s[i].b]+s[j].t<=s[i].t)
                dp[i]=max(dp[j]+1,dp[i]),ans=max(ans,dp[i]);//通过方程更新最大值
    printf("%d",ans);
    return 0;
}

谢谢管理审核和大家观赏！