Codeforces Beta Round #6 (Div. 2 Only) D. Lizards and Basements 2

제목의 대의.

한 줄로 늘어선 n명의 궁수가 있고, i번째 궁수는hi의 혈액량을 가지고 있다.주인공은 화구술로 궁수를 공격할 수 있다.직접 공격을 받은 궁수 i는 a점 데미지를 입고, 동시에 i-3-1개와 i+1개 궁수는 b점 데미지를 입는다.궁수의 혈액량이 0보다 적으면 궁수가 죽는다.최소 몇 개의 화구술을 방출해야 하는지, 각 화구술은 몇 명의 궁수를 공격한다.

문제풀이의 방향

이것은 동태적인 기획 문제다.4차원 dp 그룹을 정의합니다.dp[i][j][k][l]에 대해 말하자면 i-4-1명의 궁수의 혈액량은 j이고, i번째 궁수의 혈액량은 k이며, i+1명의 궁수의 혈액량은 l일 때 화구를 방출하는 최소 수량이다.초기치 dp[1][h[0][h[1]][h[2]]=0이고 나머지는 무한대이며 그 중에서 h[i]는 제i의 궁수의 혈액량을 대표한다.

제목 코드

#include <set>
#include <map>
#include <queue>
#include <math.h>
#include <vector>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <cctype>
#include <algorithm>
#include <time.h>
#define eps 1e-10
#define pi acos(-1.0)
#define inf 107374182
#define inf64 1152921504606846976
#define lc l,m,tr<<1
#define rc m + 1,r,tr<<1|1
#define zero(a) fabs(a)<eps
#define iabs(x) ((x) > 0 ? (x) : -(x))
#define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (min(SIZE,sizeof(A))))
#define clearall(A, X) memset(A, X, sizeof(A))
#define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE))
#define memcopyall(A, X) memcpy(A , X ,sizeof(X))
#define max( x, y ) ( ((x) > (y)) ? (x) : (y) )
#define min( x, y ) ( ((x) < (y)) ? (x) : (y) )
using namespace std;

int n,a,b,h[15];

int dp[15][20][20][20];

struct node
{
    int i,j,k,l;
} p[15][20][20][20],temp;

int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&h[i]);
        h[i]++;
    }
    clearall(dp,0x3f);
    dp[1][h[0]][h[1]][h[2]]=0;
    int x,y,z,d1,d2,d3,init = dp[0][0][0][0];
    //cout<<init;
    for(int i=1; i<n-1; i++)
    {
        for(int j=h[i-1]; j>=0; j--)
        {
            for(int k=h[i]; k>=0; k--)
            {
                for(int l=h[i+1]; l>=0; l--)
                {
                    if(dp[i][j][k][l]!=init)
                    {
                        d1=max(0,j-b);
                        d2=max(0,k-a);
                        d3=max(0,l-b);
                        if(dp[i][d1][d2][d3]>dp[i][j][k][l]+1)
                        {
                            dp[i][d1][d2][d3]=dp[i][j][k][l]+1;
                            p[i][d1][d2][d3].j=j;
                            p[i][d1][d2][d3].k=k;
                            p[i][d1][d2][d3].l=l;
                            p[i][d1][d2][d3].i=i;
                        }
                        if(d1==0&&dp[i+1][d2][d3][h[i+2]]>dp[i][j][k][l]+1)
                        {
                            dp[i+1][d2][d3][h[i+2]]=dp[i][j][k][l]+1;
                            p[i+1][d2][d3][h[i+2]].i=i;
                            p[i+1][d2][d3][h[i+2]].j=j;
                            p[i+1][d2][d3][h[i+2]].k=k;
                            p[i+1][d2][d3][h[i+2]].l=l;
                        }
                        if(j==0&&dp[i+1][k][l][h[i+2]]>dp[i][j][k][l])
                        {
                            dp[i+1][k][l][h[i+2]]=dp[i][j][k][l];
                            p[i+1][k][l][h[i+2]]=p[i][j][k][l];
                        }
                    }
                }
            }
        }
    }

    printf("%d
",dp[n-1][0][0][0]);
    temp.i=n-1;
    temp.j=0;
    temp.k=0;
    temp.l=0;
    while(!(temp.i==1&&temp.j==h[0]&&temp.k==h[1]&&temp.l==h[2]))
    {
        temp = p[temp.i][temp.j][temp.k][temp.l];
        printf("%d ",temp.i+1);
    }
    return 0;
}