求解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个回答

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

youhebke52011
youhebuke52011 我是用dfs的 100以后就很慢了 dp呀 求大神指教 求dp推导公式
接近 4 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问