NOI1999生日蛋糕

发表于 更新于 分类于 阅读次数：

NOI1999 生日蛋糕 下午在机房+晚上在家，终于干掉了，果然我是蒟蒻…… 思路：DFS+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define rint register int
using namespace std;

int N,M;
const int INF=1<<30;
int min_v[20];
int ans=INF;

void dfs(int m,int r,int h,int V,int S){
    if(m==0){
        if(V==N) ans=min(ans,S);
        return;
    }
    if(V+min_v[m]>N) return;
    if(S+(N-V)/r*2>ans) return;
    if(r<mh<m) return;
    rint s,v;
    for(rint i=r;i>=m;--i){
        for(rint j=h;j>=m;--j){
            v=V+i*i*j;
            s=S+i*2*j;
            if(m==M) s+=i*i;
            dfs(m-1,i-1,j-1,v,s);
        }
    }
}

int main(){
    cin>>N>>M;
    for(rint i=1;i<20;++i){
        min_v[i]=min_v[i-1]+i*i*i;
    }
    int r=(N-min_v[M-1])/M,h=r/M;
    dfs(M,r,h,0,0);
    if(ans==INF) cout<<0;
    else cout<<ans;
    cout<<endl;
    return 0;
}