[동적 계획] UVA111 - History Grading
4187 단어 알고리즘 경연 입문 경전알고리즘 경쟁
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:
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가지 가능한 이송 방법이 있습니다.
예를 들어 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<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
ffs와 bfs가 미로를 걷다데이터 출력 ffs 코드:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.