youhebuke52011 2016-03-16 08:03 采纳率: 0%
浏览 1751

求解acm题目,一直时间超限,求更优的算法

图片说明

 #include<cstdio>
#include<cstring>
int v[10000];
int a[10000];
int s;

int check(int k)
{
    for(int i=0;i<s;i++)
        if(k == a[i])
            return 0;
    return 1;
}

void dfs(int t,int n,int k)
{
    if(n==0){
        if(check(k)){
            a[s++] = k;
            //for(int i=0;i<k;i++)
                //printf("%d ",v[i]);
            //printf("\n");
        }
        return ;
    }
    for(int i=t;i>=1;i--){
        if( n>=i*i*i){
            //v[i] = 1;
            v[k] = i;
            dfs(t,n-i*i*i,k+1);
            //v[i] = 0;
            v[k] = 0;
        }
    }
}

int main()
{
    int n;
    int t;
    int flag;
    while(~scanf("%d",&n)){

    s = 0;
    flag = 0;
    memset(v,0,sizeof(v));
    memset(a,0,sizeof(a));
    for(int i=1;;i++){
        if(i*i*i>=n){
            if(i*i*i==n)
                flag = 1;
            t = i;
            break;
        }
    }
    if(!flag)
        t = t - 1;
    //printf("t=%d\n",t);
    dfs(t,n,0);
    //for(int i=0;i<s;i++)
        //printf("%d ",a[i]);
    //printf("\n");
    printf("%d\n",s);
    //n++;
    }
    return 0;
}


  • 写回答

1条回答

  • threenewbee 2016-03-16 10:33
    关注

    这个题目要用动态规划,不知道你怎么写的,应该先算出1~N(N^3<=n)的立方和
    然后再对它们排列组合。

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题