Vijos P1297 生日蛋糕 NOI1999

本文主要是介绍Vijos P1297 生日蛋糕 NOI1999，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

居然又是搜索题

本来以为是贪心

后来发现搜索加剪枝 轻松过

剪枝大法好!!!!!!!!!!!!!

注意题目中的 pi是常数 派  我开始以为是单位啥的..

#include <iostream>
using namespace std;
int n,m;
int min_s=1000000000;
int SS[25],VV[25];
void dfs(int s,int v,int f,int last_h,int last_r)
{
//	cout<<s<<' '<<v<<' '<<f<<endl;if(s+SS[f]>=min_s) return ;if(v+VV[f]>n) return ;if(f==0){if(v==n) min_s=s;//,cout<<s<<endl;return ;}for(int h=f;v+h*f*f+VV[f-1]<=n&&h<last_h;h++){for(int r=f;v+h*r*r+VV[f-1]<=n&&r<last_r;r++){int tmp=0;if(f==m) tmp=r*r;dfs(s+tmp+2*r*h,v+r*r*h,f-1,h,r);}}
}
int main()
{cin >>n >>m;for(int i=1;i<=m;i++){SS[i]=SS[i-1]+2*i*i;VV[i]=VV[i-1]+i*i*i;}dfs(0,0,m,1000000000,1000000000);if(min_s==1000000000) cout<<0<<endl;else cout<<min_s<<endl;return 0;
}

这篇关于Vijos P1297 生日蛋糕 NOI1999的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---