51nod 1489 蜥蜴和地下室(dp)

传送门

题意

分析

dp[12][20][20][20]; // dp[a][b][c][d]第a个弓箭手面临第a-1、a、a+1个弓箭手的生命值分别为b、c、d的状态

转移巧妙，需注意

trick

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int inf = 0x3f3f3f3f;

#define A(p) (p-a>0)?p-a:0

#define B(p) (p-b>0)?p-b:0

#define F(i,a,b) for(int i=a;i<=b;++i)

int dp[12][20][20][20];

int life[12];

int main()

{

    int n,a,b;

    scanf("%d %d %d",&n,&a,&b);

    int cost1,costn;

    memset(dp,0x3f,sizeof(dp));

    F(i,0,n-1)

    {

        scanf("%d",life+i);

        life[i]++;

    }

    cost1=(life[0]%b==0)?life[0]/b:life[0]/b+1;

    life[0]=0;

    life[1]=(life[1]-cost1*a>0)?life[1]-cost1*a:0;

    life[2]=(life[2]-cost1*b>0)?life[2]-cost1*b:0;

    costn=(life[n-1]%b==0)?life[n-1]/b:life[n-1]/b+1;

    life[n-1]=0;

    life[n-2]=(life[n-2]-costn*a>0)?life[n-2]-costn*a:0;

    life[n-3]=(life[n-3]-costn*b>0)?life[n-3]-costn*b:0;

    dp[1][0][life[1]][life[2]]=0;

    for(int k=1;k<n-1;++k)

        for(int i=16;i>=0;--i)

            for(int j=16;j>=0;--j)

                for(int t=16;t>=0;--t) if(dp[k][i][j][t]!=inf)

    {

        for(int u=i,v=j,w=t;(u||v||w);)

        {

            dp[k][B(u)][A(v)][B(w)]=min(dp[k][u][v][w]+1,dp[k][B(u)][A(v)][B(w)]);

            u=B(u),v=A(v),w=B(w);

        }

        if(i==0)  dp[k + 1][j][t][life[k + 2]] = min(dp[k + 1][j][t][life[k + 2]], dp[k][i][j][t]);

    }

    printf("%d\n",dp[n-1][0][0][0]+cost1+costn);

}

巴特西

51nod 1489 蜥蜴和地下室(dp)

传送门

题意

分析

trick

代码

最新文章

热门文章