HDU 1052 Tian Ji-The Horse Racing [욕심은 동적 기획에서의 활용]
7694 단어 동적 기획
이 문제는 분명히 이분도가 가장 잘 일치하는 문제로 바뀔 수 있다.전기의 말을 왼쪽에 놓고 제왕의 말을 오른쪽에 놓아라.전기의 말 A와 제왕의 B 사이에 전기의 말이 이기면 연달아 200의 변을 가진다.만약 무승부라면 0의 변까지 이어진다.지면 200의 모서리까지 연결됩니다.그러나 우리는 이분도의 가장 좋은 일치 알고리즘의 복잡도가 매우 높아 N=2000의 요구를 만족시킬 수 없다는 것을 안다.우리는 욕심 사상으로 문제를 분석해도 무방하다.전기가 경기의'주도권'을 쥐고 있기 때문에 그는 항상 제왕이 낸 말에 따라 자신의 말을 분배하기 때문에 여기서 제왕의 출전 순서가 말의 속도에 따라 높게부터 낮게까지 나온다고 생각해도 무방하다.이러한 가설에서 우리는 다음과 같은 욕심 전략을 귀납해 냈다.
1. 만약 전기가 남은 말 중 가장 강한 말이 제왕이 남은 가장 강한 말을 이길 수 없다면 가장 나쁜 말로 제왕의 가장 강한 말에게 져야 한다.2、만약 전기가 남은 말 중 가장 강한 말이 제왕이 남은 가장 강한 말을 이길 수 있다면 이 말로 제왕이 남은 가장 강한 말을 이길 수 있다.3. 만약 전기가 남은 말 중 가장 강한 말과 제왕이 남은 가장 강한 말이 비겼다면 비겼거나 가장 나쁜 말로 시합에서 지는 것을 선택할 수 있다.
첫 번째 욕심 전략의 증명: 이때 전기의 모든 말은 제왕의 말을 이길 수 없기 때문에 가장 느린 말로 지든 가장 빠른 말로 지든 똑같이 진다. 욕심이 많은 생각에 우리는 비교적 강한 말을 보류해야 한다. 따라서 가장 느린 말로 지든 다른 말로 지는 것보다 나쁘지 않기 때문에 이것이 가장 좋은 전략이다.증명이 끝나다.
두 번째 욕심 전략의 증명: 만약에 지금 제왕이 남은 가장 강한 말이 A이고 전기가 남은 가장 강한 말이 B라고 가정하면 만약에 더 좋은 경기 전략이 존재하여 B의 상대가 A가 아니라 전기가 더 많은 돈을 얻게 한다면 이때 A의 상대는 b이고 B의 상대는 a:1, 만약에 b>A라면 B>a, b>A가 있다.이 결과는 B>A, b>a와 같다.2、a
세 번째 욕심 전략의 증명: 전기가 가장 빠른 말도 제왕의 말과 비겼기 때문에 전기는 비기거나 질 수밖에 없다. 비기면 당연히 가장 빠른 말로 비길 수밖에 없다.지는 것을 선택하면 가장 느린 말로 지는 것이 가치가 있다. 이것은 첫 번째 욕심 전략의 사고방식과 같다.증명이 끝나다.
우리는 세 번째 욕심 전략에 비기거나 지는 것이 나타났다는 것을 발견했다.만약 모든 상황을 궁리한다면 알고리즘의 복잡도는 2분도의 최적합을 구하는 것보다 더 높을 것이다.만약 일률적으로 최강의 말을 비기거나 최악의 말을 비기게 한다면 반례가 존재한다. 光이 비겼다면 제왕마의 속도가 각각 123이고 전기마의 속도도 123이다. 매번 비기기를 선택하면 전기는 한 푼도 얻지 못한다. 그러나 속도가 1인 말을 3인 말에게 먼저 지면 200냥의 황금을 얻을 수 있다.光이 졌다면 제왕마의 속도가 각각 13, 전기마의 속도가 각각 23이었다면 전기는 1승 1패로 여전히 한 푼도 받지 못했을 것이다.속도가 3인 말로 먼저 비기면 황금 200냥을 얻을 수 있다.
세 번째 욕심에 갈래가 생겼기 때문에 우리는 이런 방법에 따라 완전히 욕심을 내는 방법을 직접 설계할 수 없다. 그러나 상술한 세 가지 욕심 전략을 통해 제왕의 말이 속도에 따라 순서를 정한 다음에 높은 말에서 낮은 말로 파견된다면 전기는 반드시 그의 말을 속도에 따라 순서를 정한 다음에 양쪽에서 말을 가져와 제왕의 말과 시합을 해야 한다는 것을 알 수 있다.이 정보가 나온 후에 동적 기획의 모델도 나왔다!f[i,j]를 설정하면 제왕은 강에서 약까지의 순서에 따라 출전과 전기가 i경기를 한 후에'머리'에서 j마리의 비교적 강한 말을 얻었고'꼬리'에서 i-j마리의 비교적 약한 말을 얻었기 때문에 얻을 수 있는 최대 이윤을 얻었다.상태 이동 방정식은 다음과 같다. f[i][j]=max(f[i-1][j]+g[n-(i-j)+1][i], f[i-1][j-1]+g[j][i]).그 중에서 g[i,j]는 전기의 말과 제왕의 말이 각각 강에서 약으로 순서를 정한 다음에 전기의 i번째 말과 제왕의 j번째 말이 경주에서 얻은 이윤은 200승에서 200승으로 지고 0으로 비겼다.본 문제 소결: 본 문제는 직접적인 욕심을 내는 방법이 존재하지만 하나의 예로 사람들에게 욕심 전략을 합리적으로 활용하고 문제의 본질을 분석한 후에 동태적인 기획으로 할 수 없을 것 같은 문제들은 교묘하게 상태를 확립하고 동태적인 기획으로 해답을 구할 수 있다.
보충: 상태 이동 방정식
f[i][j]=max(f[i-1][j]+g[n-(i-j)+1][i],f[i-1][j-1]+g[j][i]);
두 가지 특별한 상황이 있을 거예요.
1 i차전까지 진행할 때 처음부터 말 0마리를 뽑으면 모든 말이 뒤에서 뽑히면 f[i][j]=f[i-1][j]+g[n-(i-j)+1][i];
그중 n-(i-j)+1은 꼬리에서 따온 (i-j) 말이 전체 순서가 정해진 말 중 몇 번째 말인지 나타낸다
예컨대 총 8마리의 말이 있는데 4차전까지 진행되었을 때 처음부터 0마리의 말을 얻었는데, 이는 말에서 4마리의 말을 꺼내야 한다는 뜻이다
1 2 3 4 5 6 7 8
즉 번호가 5인 이 말을 5=8-(4-0)+1으로 뽑아야 한다.그러면 f[4][0]=f[3][0]+g[8-(4-0)+1][4]
2 i차전까지 진행할 때 처음부터 i마리의 말을 뽑았는데 처음부터 뽑은 말이 f[i][j]=f[i-1][j-1]+g[j][i]임을 나타냈다.
Tian Ji -- The Horse Racing
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 19321 Accepted Submission(s): 5641
Problem Description
Here is a famous story in Chinese history.
"That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others."
"Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser."
"Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian's. As a result, each time the king takes six hundred silver dollars from Tian."
"Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match."
"It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king's regular, and his super beat the king's plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?"
Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian's horses on one side, and the king's horses on the other. Whenever one of Tian's horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching...
However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses --- a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.
In this problem, you are asked to write a program to solve this special case of matching problem.
Input
The input consists of up to 50 test cases. Each case starts with a positive integer n (n <= 1000) on the first line, which is the number of horses on each side. The next n integers on the second line are the speeds of Tian’s horses. Then the next n integers on the third line are the speeds of the king’s horses. The input ends with a line that has a single 0 after the last test case.
Output
For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.
Sample Input
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
Sample Output
200 0 0
#include<stdio.h>
#include<string.h>
int tian[1005],king[1005],g[1005][1005],f[1005][1005];
void bubblesort(int a[],int n)
{
int i,j,t;
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
if(a[i]<a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int n,i,j,maxx;
while(scanf("%d",&n)!=EOF&&n) // 0
{
for(i=1;i<=n;i++)
scanf("%d",&tian[i]);
for(i=1;i<=n;i++)
scanf("%d",&king[i]);
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
bubblesort(king,n);
bubblesort(tian,n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(tian[i]>king[j])
g[i][j]=200;
else if(tian[i]<king[j])
g[i][j]=-200;
else
g[i][j]=0;
}
}
for(i=1;i<=n;i++)
{
for(j=0;j<=i;j++)
{
if(j==0)
f[i][j]=f[i-1][j]+g[n-(i-j)+1][i];
else if(i==j)
f[i][j]=f[i-1][j-1]+g[j][i];
else
f[i][j]=max(f[i-1][j]+g[n-(i-j)+1][i],f[i-1][j-1]+g[j][i]);
}
}
maxx=-200005;
for(j=0;j<=n;j++)
{
if(f[n][j]>maxx)
maxx=f[n][j];
}
printf("%d
",maxx);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방, 완전 가방, 다중 가방 dp(동적 기획 입문 dp)01 가방은 2진법으로 직접 표시할 수 있지만 데이터 양이 너무 많으면 시간을 초과하는 것이 폭력이다.01 가방의 사상은 바로 이 물품에 대해 내가 넣은 가치가 큰지 안 넣은 가치가 큰지 비교하여 방정식 f[i][v...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
