首页 > 代码库 > UVA 11766 Racing Car Computer --DP

UVA 11766 Racing Car Computer --DP

题意:电脑记录了某一时刻每个赛车的前面和后面个有多少辆车(多个车并排时在别的车那只算一辆),问最少有多少个不合理的数据。

分析:看到n<=1000时,就尽量往DP上想吧。 

每输入一组数据a,b,如果a+b>=n肯定不行,加上自己就超过n了。否则这个车肯定在(a+1,n-b)这段区间内,所以这段区间内的车子数(cnt[][]记录)++,如果车子数大于区间长度,就不再加了。搞完输入数据后,再来DP:

定义:dp[i] :前 i 辆车最多有多少车位置合理

则有方程: dp[i] = min(dp[j]+cnt[j+1][i]) (0<= j < i )

即前 i 辆车最多的合理位置车数等于前 j 辆车最多合理位置车数加上 j~i 这段位置中的合理位置车数(cnt[][]记录的都是合理位置车数)

代码:

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define N 1507int dp[N];int cnt[N][N];int main(){    int cs = 1,n,i,j;    int a,b;    while(scanf("%d",&n)!=EOF && n)    {        memset(cnt,0,sizeof(cnt));        memset(dp,0,sizeof(dp));        for(i=1;i<=n;i++)        {            scanf("%d%d",&a,&b);            if(a+b >= n)                continue;            cnt[a+1][n-b]++;            if(cnt[a+1][n-b] > n-b-a)   //不能超过区间长度                cnt[a+1][n-b] = n-b-a;        }        for(i=1;i<=n;i++)        {            for(j=0;j<i;j++)            {                dp[i] = max(dp[i],dp[j]+cnt[j+1][i]);            }        }        printf("Case %d: %d\n",cs++,n-dp[n]);    }    return 0;}
View Code