好吧,这把我逼疯了。我在spoj上解决了一个叫做混合物的问题。我不知道为什么我老是犯分割错误。还有一个问题是没有明确的输入结束指示符。我认为我处理得很正确,但如果我错了就纠正我。这是我的密码

#include<stdio.h>
#include<stdlib.h>

typedef struct temp
{
    int modSum;    //the modular sum of the cluster
    int smoke;     //the minimum smoke that a cluster can give.
}clusterInfo;

int fxDP(int *A,int len)
{
    int i,j,k,smoke1,smoke2;
    clusterInfo **dpArr=(clusterInfo **)malloc(sizeof(clusterInfo *)*(len-1));

    for(i=0;i<len-1;i++)
        dpArr[i]=(clusterInfo *)malloc(sizeof(clusterInfo)*(len-i-1));   //len- ( (i+2) -1)= len-i-1
    //dpArr[i] gives info of all clusters of length i+2

    //base case    for clusterLength=2
    for(i=0;i<len-1;i++)
    {
        dpArr[0][i].modSum=(A[i]+A[i+1])%100;
        dpArr[0][i].smoke=A[i]*A[i+1];
    }
    //endBase Case

    //induction
    for(i=1;i<len-1;i++)   //lengthOfCluster=i+2
    {
        for(j=0;j<len-i-1;j++)    //len-i-1+i+2-1=len
        {
            smoke1=(dpArr[i-1][j].modSum*A[j+(i+2)-1]) + dpArr[i-1][j].smoke;
            smoke2=(A[j]*dpArr[i-1][j+1].modSum)       + dpArr[i-1][j+1].smoke;

            dpArr[i][j].smoke=smoke1<smoke2 ? smoke1:smoke2 ;

            dpArr[i][j].modSum=(dpArr[i-1][j].modSum+A[j+(i+2)-1])%100;
        }

    }

    int result=dpArr[len-2][0].smoke;
    free(dpArr);
    return result;
}


int main()
{
    int *A; int len,i;
    while(1)
    {

        scanf("%d",&len);
        if(feof(stdin)) break;
        A=(int *)malloc(sizeof(int)*len);
        for(i=0;i<len;i++)
        scanf("%d",&A[i]);

        printf("%d\n",fxDP(A,len));
    }
    return 0;
}

最佳答案

int result=dpArr[len-2][0].smoke;

如果len=1会发生什么??

关于c - Spoj-混合物,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/19457251/

10-12 18:04