救救孩子我吧《P1731 [NOI1999] 生日蛋糕 玄关》
查看原帖
救救孩子我吧《P1731 [NOI1999] 生日蛋糕 玄关》
973280
Apollo0130楼主2024/7/6 09:50

劳师让我们讲代码
但我只有20分
求救

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f3f
int v,m,ans,costv[20],costs[20];

int maxv(int r,int h,int cnt){
	int sum=0;
	for(int i=0;i<cnt;i++,r--,h--){
		sum+=r*r*h;
	}
}

void dfs(int x,int curv,int curs,int lastr,int lasth){
	if(curs+costs[m-x+1]>ans) return; 
	if(x>1 && curv+maxv(lastr-1,lasth-1,m-x+1)<1)return;
	if(x==m+1){
		if(curv==v){
			ans=min(ans,curs);
		}
		return;
	}
	if(curv+costv[m-x+1]>v)return;
	for(int r=min(lastr-1,(int)sqrt(v-curv));r>=m-x+1;r--){
		for(int h=m-x+1;h<=min(lasth,(v-curv)/r/r);h++){
			if(x!=1) dfs(x+1,curv+r*r*h,curs+2*r*h,r,h);
			else dfs(x+1,curv+r*r*h,curs+2*r*h+r*r,r,h);
		}
	}
}

void premake(){
	for(int i=1;i<=m;i++){
		costv[i]=costv[i-1]+(i*i*i);
		costs[i]=costs[i-1]+2*i*i;
	}
}

int main(){
	cin>>v>>m;
	ans=INF;
	premake();
	dfs(1,0,0,INF,INF);
	cout<<(ans==INF?0:ans);
	return 0;
}
2024/7/6 09:50
加载中...