TLE求助
查看原帖
TLE求助
919754
cabbyblue楼主2024/1/11 21:18

rt,

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int ccf=19;
int n,m,x,f[ccf],m1[ccf],m2[ccf];
int dfs(int x,int y,int a1,int a2,int sum){
	if(y==0)if(x==0){f[m]=min(f[m],a1*a1-2*a1+1+sum);return a1*a1-2*a1+1+sum;}else{return 1e9;}
	if(x<m1[y])return 1e9;
	if(sum+m2[y]>f[m]||sum>f[y])return 1e9;
	int mi=1e9;
	for(int r=a1;r*r<=x;r++)for(int h=a2;h*r*r<=x;h++)mi=min(mi,dfs(x-h*r*r,y-1,r+1,h+1,sum+r*2*h)),f[y]=min(f[y],mi);
	return mi;
}
int main(){
	memset(f,0x3f,sizeof(f));
	cin>>n>>m;
	for(int i=m;i>=1;i--)
		m2[i]=m2[i+1]+(m-i+1)*(m-i+1),m1[i]=m1[i+1]+(m-i+1)*(m-i+1)*(m-i+1);
	x=dfs(n,m,1,1,0);cout<<(x>=1e9?0:x);
	return 0;
} 
2024/1/11 21:18
加载中...