[동적 계획] UVA111 - History Grading

History Grading 
Background
Many problems in Computer Science involve maximizing some measure according to constraints.
Consider a history exam in which students are asked to put several historical events into chronological order. Students who order all the events correctly will receive full credit, but how should partial credit be awarded to students who incorrectly rank one or more of the historical events?
Some possibilities for partial credit include:
  • 1 point for each event whose rank matches its correct rank
  • 1 point for each event in the longest (not necessarily contiguous) sequence of events which are in the correct order relative to each other.

  • For example, if four events are correctly ordered 1 2 3 4 then the order 1 3 2 4 would receive a score of 2 using the first method (events 1 and 4 are correctly ranked) and a score of 3 using the second method (event sequences 1 2 4 and 1 3 4 are both in the correct order relative to each other).
    In this problem you are asked to write a program to score such questions using the second method.
    The Problem
    Given the correct chronological order of n events  as  where  denotes the ranking of event i in the correct chronological order and a sequence of student responses  where  denotes the chronological rank given by the student to event i; determine the length of the longest (not necessarily contiguous) sequence of events in the student responses that are in the correct chronological order relative to each other.
    The Input
    The first line of the input will consist of one integer n indicating the number of events with  . The second line will contain nintegers, indicating the correct chronological order of n events. The remaining lines will each consist of n integers with each line representing a student's chronological ordering of the n events. All lines will contain n numbers in the range  , with each number appearing exactly once per line, and with each number separated from other numbers on the same line by one or more spaces.
    The Output
    For each student ranking of events your program should print the score for that ranking. There should be one line of output for each student ranking.
    Sample Input 1
    4
    4 2 3 1
    1 3 2 4
    3 2 1 4
    2 3 4 1

    Sample Output 1
    1
    2
    3

    Sample Input 2
    10
    3 1 2 4 9 5 10 6 8 7
    1 2 3 4 5 6 7 8 9 10
    4 7 2 3 10 6 9 1 5 8
    3 1 2 4 9 5 10 6 8 7
    2 10 1 3 8 4 9 5 7 6
    

    Sample Output 2
    6
    5
    10
    9

    제목:
    정보 과학 중 일부는 어떤 조건의 제한 하에서 계산의 최대치를 찾아내는 것에 관한 것이다.
    역사 시험으로 말하자면, 학생들은 일부 역사 사건에 대해 발생한 연대순에 따라 배열하도록 요구받는다.모든 사건의 순서가 정확한 학생은 의심할 여지없이 만점을 받을 수 있다.그런데 다 맞지 않은 분들은 어떻게 점수를 줘야 하나요?다음과 같은 2가지 가능한 이송 방법이 있습니다.
  • 표준 답안과 순서가 같은 사건마다 1점
  • 가장 긴 시퀀스 이벤트 중 상대적인 순서는 표준 답안 발견자로서 이벤트마다 1점을 받을 수 있다.

  • 예를 들어 4개의 사건이 발생하면 그 발생 시간의 순서가 1, 2, 3, 4이다.따라서 학생들이 이 4가지 사건 발생 순서가 1324라고 답하면 상기 1가지 방법에 따라 2점(첫 번째 및 네 번째 사건)을 받을 수 있다.하지만 위 두 번째 방법으로 3점을 받을 수 있다(1, 2, 4 또는 1, 3, 4의 상대적인 순서는 표준답안에서 발견할 수 있다)
    이 문제 에서, 두 번째 방법 으로 학생 이 몇 점 을 받아야 하는지 계산해 주십시오
    사고방식: 입력이 약간 빙빙 돌기 때문에 입력에 대해 약간의 변화를 해야 한다. 이것은 전형적이고 가장 긴 공공 서열 문제이다.
    #include
    #include
    
    using namespace std;
    
    int order[30];
    int node[30],arry[30][30];
    
    int main()
        {
            int num;
            cin>>num;
            int i,j,k;
            for(i=0;i>k;
                    order[k-1]=i+1;
                }
            while(cin>>k)
                {
                    node[k-1]=1;
                    for(i=1;i>k;
                            node[k-1]=i+1;
                        }
                    memset(arry,0,sizeof(arry));
                    for(i=1;i<=num;i++)
                        {
                            for(j=1;j<=num;j++)
                                {
                                    if(node[i-1]==order[j-1]) arry[i][j]=arry[i-1][j-1]+1;
                                    else arry[i][j]=max(arry[i-1][j],arry[i][j-1]);
                                }
                        }
                    cout<

    좋은 웹페이지 즐겨찾기