HBC24073成绩输入输出[USACO 2017 Feb G]Why Did the Cow Cross the Road II题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

Farmer John raisesNbreeds of cows , conveniently numbered1…N. Some pairs of breeds are friendlier than others, a property that turns out to be easily characterized in terms of breed ID: breedsaandbare friendly if|ab|≤4, and unfriendly otherwise. A long road runs through FJ's farm. There is a sequence ofNfields on one side of the road , and a sequence ofNfields on the other side of the road . To help his cows cross the road safely, FJ wants to draw crosswalks over the road. Each crosswalk should connect a field on one side of the road to a field on the other side where the two fields have friendly breed IDs . Each field can be accessible via at most one crosswalk . Given the ordering ofNfields on both sides of the road through FJ's farm, please help FJ determine the maximum number of crosswalks he can draw over his road, such that no two intersect.

Farmer John raises N breeds of cows (1≤N≤1000), conveniently numbered 1…N. Some pairs of breeds are friendlier than others, a property that turns out to be easily characterized in terms of breed ID: breeds a and b are friendly if |a−b|≤4, and unfriendly otherwise. A long road runs through FJ's farm. There is a sequence of N fields on one side of the road (one designated for each breed), and a sequence of N fields on the other side of the road (also one for each breed). To help his cows cross the road safely, FJ wants to draw crosswalks over the road. Each crosswalk should connect a field on one side of the road to a field on the other side where the two fields have friendly breed IDs (it is fine for the cows to wander into fields for other breeds, as long as they are friendly). Each field can be accessible via at most one crosswalk (so crosswalks don't meet at their endpoints). Given the ordering of N fields on both sides of the road through FJ's farm, please help FJ determine the maximum number of crosswalks he can draw over his road, such that no two intersect.

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC24073成绩输入输出[USACO 2017 Feb G]Why Did the Cow Cross the Road II题解