动态规划进阶题目之开餐馆

动态规划进阶题目之开餐馆

时间： 1ms        内存：64M

描述：

北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m₁, m₂, ... m_n 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用p_i 表示在m_i 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。

输入：

标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ，表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行,
第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000).
第2行:n 个地点的位置m1 , m2, ... mn ( 1000000 > mi > 0 且为整数,升序排列)
第3行:n 个地点的餐馆利润p1 , p2, ... pn ( 1000 > pi > 0 且为整数)

输出：

对于每组测试数据可能的最大利润

示例输入：

2
3 11
1 2 15
10 2 30
3 16
1 2 15
10 2 30

示例输出：

40
30

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}
int main()
{
    int n,l,t,i,j,dis[101],value[101],pre[101],f[101];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&l);
        memset(dis,0,sizeof(dis));
        memset(value,0,sizeof(value));
        memset(pre,0,sizeof(pre));
        memset(f,0,sizeof(f));
        for(i=1;i<=n;i++)
            scanf("%d",&dis[i]);
        for(i=1;i<=n;i++)
            scanf("%d",&value[i]);
        for(i=2;i<=n;i++)
            {
            for(j=i-1;j>=1;--j)
            if(dis[i]-dis[j]>l)
            {
                pre[i]=j;
                break;
            }
    }
    f[1]=value[1];
    for(i=2;i<=n;i++)
        f[i]=max(f[i-1],f[pre[i]]+value[i]);
    printf("%d\n",f[n]);
}
return 0;
}

参考答案（时间最优[0]）：

#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;

int dp[101];    //dp[i]表示该不该在第i个地段开餐馆
int mi[101];
int pi[101];
int pre[101];   //pre[i]表示当在第i个地段开餐馆的时候它的前一个可以开餐馆的地方
int main()
{
    int t;
    cin >> t;
    while( t-- )
    {
        int m , n ;
        cin >> m >> n;
        memset(mi,0,sizeof(mi));
        memset(pi,0,sizeof(pi));
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        for( int i = 1 ; i <= m ; i++)
            cin >> mi[i];
        for( int i = 1 ; i <= m ; i++)
            cin >> pi[i];
        for( int i = 2 ; i <= m ; i++)
            for( int j = i - 1 ; j >= 1 ; j--)
                if(mi[i] - mi[j] > n )
                {
                    pre[i] = j;
                    break;
                }
        dp[1] = pi[1];
        for( int i = 2 ; i <= m ; i++)
            dp[i] = max(dp[i-1],dp[pre[i]]+pi[i]);
        cout << dp[m] << endl;
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。