[COGS 396]魔术球问题(简化版)

danihao123 posted @ 2016年8月27日 22:55 in 题解 with tags COGS 贪心 , 134 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这简化的真彻底……变成一个贪心水体了……

枚举柱子数,然后每次尽可能放球,放不了球了增加柱子,增加不了了就是最优解:

代码:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=61;
vector<int> V[maxn];
inline bool isSqr(int x){
    register int temp=floor(sqrt(x));
    return temp*temp==x;
}
int main(){
    int n,temp;
    bool flag;
    register int i,j,ans=1;
    freopen("balla.in","r",stdin);
    freopen("balla.out","w+",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        while(true){
            flag=false;
            for(j=0;j<i;j++){
                if(V[j].empty() || isSqr(V[j].back()+ans)){
                    V[j].push_back(ans++);
                    flag=true;
                    break;
                }
            }
            if(!flag)
                break;
        }
    }
    printf("%d\n",ans-1);
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter