uva 11766 Racing Car Computer

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【重做DP系列】 区间DP

题意:有n个汽车在比赛,给出每个汽车会显示它前面有a个汽车后面有b个汽车,汽车可以并排走,但是不会显示。但是有些汽车的显示是错误的,或者和其他汽车的信息在一起的时候就会产生矛盾。问题是选出最少的汽车的信息是错误的或者矛盾的,输出个数即可

这题算是做过了,要转化为区间DP来做,转化其实有些难度。

给汽车排位,注意是排位而不是排名,好像5个汽车比赛,有2个并排的,他们再第2名,那么排位情况1 2 2 3 4,采取了排位后,就可以给每个汽车设置一个位置,而消除了所谓的并排。所以我们给每个汽车定一个区间,他必然在这个区间的位置内。好像第2名的汽车,它必然在位置【2,3】内,至于具体在哪个位置没关系,排名不分先后,因为这个区间内的汽车都是并排的(实际情况下)

所以对于每个汽车,就可以给定一个区间。前面a车,后面b车,那么它所在区间就是【a+1,b】,所以我们就能给每个区间统计有多少汽车。但是一个区间的汽车数不能过多,w[x][y] <= y - x + 1 , 因为这个区间内最多这么多汽车。当然在统计的时候,有些汽车是能直接抛弃的。好像5个汽车,有个汽车前面3车,后面3车,这是不可能的,因为加上它自己都超过5个车了,这些区间要直接去掉。

题目要找出最小的汽车的信息是错的,换过来就是最多的汽车是可以共存的,没有矛盾。这样就引发了区间DP,在一个总区间内,利用所给的小区间去覆盖它,每个小区间是有权值的即w[x][y],在不重复覆盖的情况下使得权值和最大

为什么要不能重复覆盖,看个例子

5个汽车,A汽车的区间为[2,3],也就是它前面有1个汽车,后面有2个汽车;B汽车的区间为[3,4],也就是它前面有2个汽车,后面有1个汽车

因为两个汽车区间不同,它们是不可能并排的,而且可知A在前面。另外可知,跟A并排的有1个汽车,跟B并排的也是一个汽车,所以汽车总数已经是1 + 2 + 2 + 1 = 6 了。而且单看前面的,A前面一个汽车,A并排的包括自己2个汽车,一共3个汽车,这些都在B前面,所以有3个汽车在B前面,但这和B前面有2个汽车是矛盾的

状态转移方程

dp[i] = max{ dp[j] + w[j+1][i] }

dp[i]的意义是1到i的区间被覆盖(不一定完全覆盖,但不能重复)能产生的最大权值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1010
#define cl memset

int n;
int dp[N];
int w[N][N];
int a[N],b[N];

int main(){
int cas = 0;
while(scanf("%d",&n)!=EOF && n){
cl(dp,0,sizeof(dp));
cl(w,0,sizeof(w));
for(int i = 0; i < n; i++){
int x,y;
scanf("%d%d",&x,&y);
if(x + y >= n) continue;
w[x+1][n-y]++;
if(w[x+1][n-y] > n - x - y)
w[x+1][n-y] = n - x - y;
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++)
dp[i] = max(dp[i] , dp[j] + w[j+1][i]);
}
printf("Case %d: %d\n",++cas,n-dp[n]);
}
return 0;
}