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;
}