hdu-4597(게임 DP)
두 아이가 모두 똑똑하기 때문에 그들은 반드시 가능한 한 최선의 방안을 선택할 것이다. 그래서 모든 사람의 현재의 최선은 다음 사람의 최선에 의존한다.그럼 디테일은 어떻게 할까요?아니면 케케묵은 곡조를 다시 연주할지, 먼저 상태를 어떻게 표시할지, 상태를 어떻게 옮길지 생각해 보자.
상태를 완전하게 묘사하려면, 우리는 반드시 4차원 그룹을 만들어 두 무더기의 현재 상태를 기록해야 한다.그러면 상태는 d[al][ar][bl][br]로 표시하기 어렵지 않다. 두 무더기의 카드가 현재 수미 상황에서 얻을 수 있는 최대 점수를 나타낸다. 그러면 상태는 어떻게 이동합니까?
앞에서 말했듯이 현재의 최우해는 이전의 최우해에 의존한다. 왜냐하면 두 아이가 모두 똑똑하기 때문이다.추DP는 항상 컨디션이 무엇을 표시하는지 주의해야 한다. 방금 이 아이의 최대 점수를 표시한다고 했는데 어떻게 구하지?분명히 총점에서 다음 아이의 득점을 빼고 다음 아이의'총점'은 현재 아이가 가져간 패를 빼야 한다.
자세한 참고 코드:
#include
using namespace std;
int T,n,d[25][25][25][25],a[25],b[25];
int dp(int al,int ar,int bl,int br,int sum) {
int& ans = d[al][ar][bl][br];
if(ans != -1) return ans;
ans = 0;
if(al<=ar) {
ans = max(ans,sum-dp(al+1,ar,bl,br,sum-a[al]));
ans = max(ans,sum-dp(al,ar-1,bl,br,sum-a[ar]));
}
if(bl<=br) {
ans = max(ans,sum-dp(al,ar,bl+1,br,sum-b[bl]));
ans = max(ans,sum-dp(al,ar,bl,br-1,sum-b[br]));
}
return ans;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int sum = 0;
memset(d,-1,sizeof(d));
for(int i=1;i<=n;i++) scanf("%d",&a[i]) , sum += a[i];
for(int i=1;i<=n;i++) scanf("%d",&b[i]) , sum += b[i];
int ans = dp(1,n,1,n,sum);
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
조밀한 게임을 Scratch로 만들어 보았다. 그 1.2021년 1월 7일에 스가 총리가 긴급 사태 선언을 발령했습니다. 역시 「밀」이 좋지 않은 일이라고, 재차 생각했으므로 넷에서 보인 명작 을 마음대로 흉내내 Scratch로 만들어 보았습니다. <완성 이미지> 링크...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
