0

任务是通过选择输入的订单来计算 48 小时时间段内可能的最大成本。以不重叠的方式选择订单。

例如，如果输入如下

4

1 2 100

2 3 200

3 4 1600

1 3 2100

然后通过选择 last 2 events 输出将是 3700。

请注意，在重叠事件的情况下，仅应选择会产生最大成本的事件。

输入

输入的第一行包含一个整数 T，即测试用例的数量。T 测试用例如下。测试用例的第一行包含一个整数 N，即接收到的用于执行事件的订单数。接下来的 N 行中的每一行都包含三个空格分隔的整数 Si、Ei、Ci，它们是问题陈述中描述的第 i 个事件的参数。约束

1≤T≤10

1≤N≤2000

0 ≤ Si < Ei ≤ 48

0 ≤ Ci ≤ 10^6

输出

每个测试用例的输出应在单独的行中包含一个整数，这是可能的最大成本。

这是一个标准的DP问题这是我的代码。我已经测试了我能想到的所有可能的测试用例，但是当我将此代码提交给在线法官时，我得到了错误的答案。请帮忙。

#include<iostream>
#include<stdio.h>
using namespace std;
unsigned long long A[50][50];
int main()
{
int t,m,S,E,C,i,j;
unsigned long long cost;

 scanf("%d",&t);
while(t--)
{

    int n=-1;


    scanf("%d",&m);

    for(i=0;i<50;++i)
    for(j=i;j<50;++j)
    A[i][j]=0;

    while(m--)
    {

        scanf("%d%d%d",&S,&E,&C);
        A[S][E]=C;
        if(E>n)
        n=E;
    }

    for(int l=2;l<=(n+1);++l)
    {
        for(i=0;i<=(n-l+1);++i)
        {
            j=i+l-1;

            for(int k=i;k<=j;++k)
            {
                cost=A[i][k]+A[k][j];
                if(cost>A[i][j])
                {
                    A[i][j]=cost;

                }
            }
        }
    }
   cout<<A[0][n]<<endl;


}

}
4

1 回答 1

2

您没有考虑以下事项： 请注意，在重叠事件的情况下，仅应选择会产生最大成本的事件

您使用的逻辑是正确的。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
unsigned long long A[50][50];
int main()
{
int t,m,S,E,C,i,j;
unsigned long long cost;

 scanf("%d",&t);
while(t--)
{

    int n=-1;


    scanf("%d",&m);

    /*for(i=0;i<50;++i)
    for(j=i;j<50;++j)
    A[i][j]=0;
    */
    memset(A,0,sizeof(A));

    while(m--)
    {

        scanf("%d%d%d",&S,&E,&C);
        A[S][E]= (C>A[S][E])?C:A[S][E];
        if(E>n)
        n=E;
    }

    for(int l=2;l<=(n+1);++l)
    {
        for(i=0;i<=(n-l+1);++i)
        {
            j=i+l-1;

            for(int k=i;k<=j;++k)
            {
                cost=A[i][k]+A[k][j];
                if(cost>A[i][j])
                {
                    A[i][j]=cost;

                }
            }
        }
    }
   cout<<A[0][n]<<endl;


}

}
于 2012-10-06T20:37:57.273 回答