2019.3.17周末省选模拟爆零赛

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

3.17周末训练

---

Code

~ Wolf ~

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
int n,attack;
struct wolf_data
{
	int atk,bonus,hp;
}w[410];
int times[410];
int f[910][910];
int main(int argc, char const *argv[])
{
	freopen("wolf.in","r",stdin);
	freopen("wolf.out","w",stdout);
	n=read(),attack=read();
	for(int i=1;i<=n;++i)
		w[i].atk=read(),w[i].bonus=read(),w[i].hp=read(),times[i]=(w[i].hp/attack)+(w[i].hp%attack!=0);
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i) f[i][i]=times[i]*(w[i].atk+w[i-1].bonus+w[i+1].bonus);
	for(int i=1;i<=n+10;++i) f[i][i-1]=0;
	for(int i=2;i<=n;++i)
		for(int len=1;len<=n-i+1;++len)
		{
			int j=i+len-1;
			for(int k=len;k<=j;++k)
			f[len][j]=min(f[len][j],f[len][k-1]+f[k+1][j]+(w[k].atk+w[len-1].bonus+w[j+1].bonus)*times[k]);
		}
	cout<<f[1][n]<<endl;
	return 0;
}

~ Sum ~

~ RSMT ~（提交答案）

---