Racing Car Computer (区间dp)

Racing Car Computer (区间dp)

The racing cars of today are equipped with so many sophisticated equipment. Introduction of a newvisual transducer which is interfaced with the on-board computer can tell you on the fly how manycars are ahead of you while how many are trailing. There are N cars on a racing track. Each has anon-board computer with the new feature. During the race, every single car’s computer keeps displayingtwo integers, a (The number of cars in front of him) & b (The number of cars behind him) for aparticular moment. It is possible that at some time, some of the cars are racing side by side i.e. theyare exactly at the same location. A car will not consider any other car at the same location to be aleading or trailing car.Now, it is suspected that some of the new transducers are not working properly inside such highspeed vehicles. The report with all computers’ data generated at a particular timestamp is reported toyou. You are to determine the minimum number of cars that have faulty data.InputEach test case begins with an integer N (1 ≤ N ≤ 1000), the number of cars on a track. The next Nlines each has two integers — a & b (0 ≤ a, b ≤ 1500) for a particular car.The last test case is followed by a line with a single ‘0’ indicating the end of input.OutputFor each test case, print a line in the format, ‘Case X: Y ’, where X is the case number & Y is theminimum number of cars that must have faulty data according to the report.Sample Input42 20 00 23 111 10Sample OutputCase 1: 3Case 2: 1

题目大概：

给出n辆车，每辆车给出在它前面的车的数量和在它后面的车的数量，然后求最少有多少车给出的位置信息是错误的。

思路：

可以从反面考虑，那就是求最多的合法的车的数量。

因为给出了前面a 辆车，后面 b 辆车，所以它一定在一个区间范围内，【a+1，n-b】，并且是在任何一个位置都应该没有问题，如果两辆车合法的话，它们的区间一定不会相交，因为会有冲突，即如果两练车有相交的部分，我们在求解合法车的时候，选了1号，就不能选2号。所以合法的区间一定相离，那么就用区间dp，枚举每个区间就行了。

但有一个地方要注意，就是一个区间【j，i】，最多的车的数量是i-j+1，因为在这个区间最多放这些车，就是最多有并排的这些车。

代码：

#include using namespace std;const int maxn=1050;int a[maxn][maxn];int dp[maxn];int main(){ int n; int ans=1; while(scanf("%d",&n)&&n) { int u,v; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { scanf("%d%d",&u,&v); a[u+1][n-v]++; } memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { for(int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。