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

时间:2022-06-24 21:28:41

dp[i][j][k]表示当前要打第i个怪,第i-1个怪的生命值为j,第i个怪的生命值为k,1到i-2的怪全死了所需的最小代价是多少。那么当前至少要打 (j+b-1)/b下,最多就是把i-1,i,i+1三个怪都打死的次数,这样枚举打的次数去转移就可以了。注意到题目要求怪的生命值在0一下才会死,我们这里认为怪的生命值归零就死,开始的时候把每个生命值都加1就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define maxn 250009
#define INF 1e9
using namespace std;
int dp[15][20][20],n,a,b,h[20];
int X[15][20][20],Y[15][20][20];
void output(int dep,int x,int y)
{
	if(dep==2)
		return ;
	output(dep-1,X[dep][x][y],Y[dep][x][y]);
	for(int i=0;i<dp[dep][x][y]-dp[dep-1][X[dep][x][y]][Y[dep][x][y]];i++)
		printf("%d ",dep-1);
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++)
		scanf("%d",&h[i]),h[i]++;
	for(int i=0;i<=n;i++) for(int j=0;j<=16;j++) for(int k=0;k<=16;k++) dp[i][j][k]=INF;
	dp[2][h[1]][h[2]]=0;
	for(int i=2;i<n;i++)
	{
		for(int j=0;j<=h[i-1];j++)
		{
			for(int k=0;k<=h[i];k++)
			{
				if(dp[i][j][k]==INF)
					continue;
				int from=(j+b-1)/b;
				int to=max(from,max((k+a-1)/a,(h[i+1]+b-1)/b));
				for(int hit=from;hit<=to;hit++)
				{
					if(dp[i+1][max(0,k-a*hit)][max(0,h[i+1]-b*hit)]>dp[i][j][k]+hit)
					{
						dp[i+1][max(0,k-a*hit)][max(0,h[i+1]-b*hit)]=dp[i][j][k]+hit;
						X[i+1][max(0,k-a*hit)][max(0,h[i+1]-b*hit)]=j;
						Y[i+1][max(0,k-a*hit)][max(0,h[i+1]-b*hit)]=k;
					}
				}
			}
		}
	}
	printf("%d\n",dp[n][0][0]);
	output(n,0,0);
	puts("");
	return 0;
}