0

タスクは、入力された注文を選択して、48 時間の期間に可能な最大コストを計算することです。注文は、重複しないように選択されます。

たとえば、入力が次の場合

4

1 2 100

2 3 200

3 4 1600

1 3 2100

最後の 2 つのイベントを選択すると、出力は 3700 になります。

イベントが重複している場合は、最大コストが発生するイベントのみを選択する必要があることに注意してください。

入力

入力の最初の行には、テスト ケースの数である整数 T が含まれます。T テスト ケースが続きます。テスト ケースの最初の行には、整数 N (イベントを実行するために受け取った注文の数) が含まれています。次の N 行のそれぞれには、スペースで区切られた 3 つの整数 Si、Ei、Ci が含まれています。これは、問題ステートメントで説明されている i 番目のイベントのパラメーターです。制約

1≦T≦10

1≦N≦2000

0≦Si＜Ei≦48

0 ≤ Ci ≤ 10^6

出力

各テスト ケースの出力には、個別の行に 1 つの整数 (可能な最大コスト) が含まれている必要があります。

これは標準的な 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 に答える