2 youhebke52011 youhebke52011 于 2016.03.16 16:03 提问

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

caozhy
caozhy   Ds   Rxr 2016.03.16 18:33

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

youhebke52011
youhebke52011 我是用dfs的 100以后就很慢了 dp呀 求大神指教 求dp推导公式
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!