POJ 1036 Gangsters（DP）

题目地址：http://poj.org/problem?id=1036

题意：宾馆有个可以伸缩的门，每秒钟可以伸长1个单位，或者缩小1个单位，或者原地不动。有N个强盗，每个强盗会在t的时间内到达并按，如果此时门的开方度和他的身材s正好相等，这个强盗就会进来，然后你就能得到p的加分。初始状态门是关闭的，让你求出在t时刻得到的最大得分。

思路：dp[i]是第i个人进来获得的最大分数，且第i个人必须进来

AC代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

const int inf = 0x7f7f7f7f;//2139062143
typedef long long ll;
using namespace std;

struct node
{
    int time;
    int value;
    int weight;
};

bool cmp(node a,node b)
{
    return a.time < b.time;
}

int dp[110];

int main()
{
    int n,k,t;
    while(scanf("%d%d%d",&n,&k,&t) != EOF)
    {
        memset(dp,0,sizeof(dp));
        node a[110];
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].time);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].value);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].weight);
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1; i<=n; i++)
        {
            if(a[i].time >= a[i].weight)
                dp[i] = a[i].value;
            for(int j=1; j<i; j++)
            {
                if(!dp[j])//要是上一个阶段的门没有达到所需要的长度，则没有可比性，需要退出
                    continue;
                if(a[i].time - a[j].time >=abs(a[i].weight - a[j].weight))//大于是因为门有可能不动
                {
                    dp[i] = max(dp[i],dp[j]+a[i].value);
                }
            }
        }
        int max1 = -1;//有可能最小值是0,
        for(int i=1; i<=n; i++)
        {
            max1 = max(max1,dp[i]);
        }
        printf("%d\n",max1);
    }
    return 0;
}
           

错误代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <climits>
#include <cmath>
#include <cctype>

const int inf = 0x7f7f7f7f;//2139062143
typedef long long ll;
using namespace std;

struct node
{
    int time;
    int value;
    int weight;
};

bool cmp(node a,node b)
{
    return a.time < b.time;
}

int dp[110];

int main()
{
    int n,k,t;
    while(scanf("%d%d%d",&n,&k,&t) != EOF)
    {
        memset(dp,0,sizeof(dp));
        node a[110];
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].time);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].value);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i].weight);
        }
        sort(a+1,a+n+1,cmp);
        for(int i=1; i<=n; i++)
        {
            if(a[i].time >= a[i].weight)
                dp[i] = a[i].value;
            for(int j=1; j<i; j++)
            {
                if(a[i].time - a[j].time >=abs(a[i].weight - a[j].weight))
                {
                    dp[i] = max(dp[i],dp[j]+a[i].value);
                }
                else
                {
                    dp[i] = max(dp[i],dp[j]);//因为他要的最大值，所以这个没必要更新，否则会导致后面错误
                }
            }
        }
        int max1 = -1;//有可能最小值是0,
        for(int i=1; i<=n; i++)
        {
            max1 = max(max1,dp[i]);
        }
        printf("%d\n",max1);
    }
    return 0;
}