게임이론+dp-로곡P2964 [USACO09NOV] 코인의 게임 A Coin Game

https://daniu.luogu.org/problem/show?pid=2964원래 바둑 이론을 몰랐는데, 지금은 dp를 끼워서 바로 시들었다.문제풀이를 한참 동안 보았다.우리는 f[i][j]를 만들어서 1~i가 남았을 때 윗사람이 j개를 골랐다.분명히 i=n은 처음부터 하나도 찾지 못했다.지금 우리는 dp를 거꾸로 읽기 때문에 처음에 우리의 읽기도 거꾸로 읽는다.이 f[i][j]에 관해서는 한 선수의 상태를 대표하기 때문에 도대체 선수인지 후수인지 우리는 모른다.그러나 답은 분명히 f[n]이다[1].즉, 현재 1~n의 물품(처음 상태)이 남았는데 지난번에 한 사람이 1개를 뽑았는데 분명히 이번에는 우리가 1개 또는 2개를 뽑을 수 있다. 이것은 우리가 처음에 제목에서 요구한 상태와 같다.그럼 f[i][j]는 어떻게 구하죠?그럼 우리 일일이 열거해서 지금 k개를 가져가자.f[i][j]=max(f[i][j],sum[i]-f[i-k][k]); f[i][j-1]는 이미 큰 영화를 계산했기 때문에 k는 j*2-1과 j*2를 일일이 열거하면 된다.

#include
#include
#include
#include
#define Ll long long
using namespace std;
int f[2005][2005],a[2005];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=n;i;i--)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)a[i]=a[i-1]+a[i];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        f[i][j]=f[i][j-1];
        int k=j*2;
        if(i>=k)f[i][j]=max(f[i][j],a[i]-f[i-k][k]);
        k=j*2-1;
        if(i>=k)f[i][j]=max(f[i][j],a[i]-f[i-k][k]);
    }
    printf("%d",f[n][1]);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

게임이론+dp-로곡P2964 [USACO09NOV] 코인의 게임 A Coin Game

좋은 웹페이지 즐겨찾기