The County Fair

题目分析

首先需要明确的是，我们要尽可能地按照礼品发放时间先后顺序考虑来拿取礼品，这样才会拿到数量更多的礼品。
这里提供一种动态规划的思路做法。我们需要用数组存储每一个集市以及它发放礼品的时间。在按照时间从小到大顺序排序（sort）之后，考虑第i个礼品拿到的情况下，前i个礼品中拿到礼品的数量，记作dp[i]。此时，需要遍历i号元素之前的所有元素。一旦时间上可以满足“从j号集市赶到i号集市，拿到i号集市的礼品”，就考虑是否更新dp[i]（考虑原来的dp[i]和dp[j]+1哪个更大）。不满足dp[i]保持不变。状态转移方程即为：

dp[i] = max(dp[i], dp[j]+1) // j小于i，

关键代码实现

typedef pair<int, int> P;	// <集市号，分发时间>

int mapt[405][405];	// t_i,j
P mak[405];

for (int i = 1; i <= n; i++)
{
    for (int j = 0; j < i; j++)
    {
        // 表示可以赶上第i个礼品发放时间
        if (mapt[mak[j].first][mak[i].first] + mak[j].second <= mak[i].second)
        {
            dp[i] = (dp[j] + 1) > dp[i] ? (dp[j] + 1) : dp[i];
        }
        // 如果赶不上，默认dp[i]保持不变，不作处理
    }
}

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int mapt[405][405];
P mak[405];
int dp[405];
int n;
int ans;

bool com(P a, P b)
{
    return a.second < b.second;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        mak[i] = { i,t };
    }
    mak[0] = { 1,0 };   // 记录初始情况，t=0，从1号集市开始
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> mapt[i][j];
        }
    }
    sort(mak + 1, mak + 1 + n, com);
   
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            //表示可以赶上第i个礼品发放时间
            if (mapt[mak[j].first][mak[i].first] + mak[j].second <= mak[i].second)
            {
                dp[i] = (dp[j] + 1) > dp[i] ? (dp[j] + 1) : dp[i];
            }
        }
    }
    
    // 注意，需要综合考虑所有的dp，取其中的最大值，因为之前的“dp[i]表示第i个礼品一定取到”只是一个假设，但是总会取到一个礼品，使得最后的礼品数量最多
    sort(dp + 1, dp + 1 + n);
    cout << dp[n] << endl;
}