「USACO 2006 Open Gold」赶集

这道题std是一个转化思想变为最长路问题解决

但是我这里提供一个$DP$思想的代码(反正值域很小)，仅供参考

#include <bits/stdc++.h>
using namespace std; 

const int N=4e2+10;

struct node
{
	int val, idx;
	
	bool operator< ( const node &a )const 
	{
		return val < a.val;
	}
	
}p[N];

int mp[N][N];
int f[N];

int main()
{
//    freopen( "txt.in","r",stdin );
	int n;
	cin>>n;
	for( int i=1;i<=n;i++ )
		cin>>p[i].val, p[i].idx=i;
	sort( p+1,p+n+1 );
	for( int i=1;i<=n;i++ )
		for( int j=1;j<=n;j++ )
			cin>>mp[i][j];
	int ans=0;
	for( int i=1;i<=n;i++ )
	{
		if( mp[1][p[i].idx] <= p[i].val )
			f[i]=1;
		for( int j=1;j<i;j++ )
            if( p[j].val+mp[p[j].idx][p[i].idx] <= p[i].val )
                f[i]=max( f[i],f[j]+1 );
        ans=max( ans,f[i] );
	}
	cout<<ans;
}