题解 | #填充数组#NC173#C

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @param k int整型 
 * @return int整型
 */
int FillArray(int* a, int aLen, int k ) {
    // write code here
    long f[aLen][k];                  //一个数组来保存会用到的值 第二行为需要填充两个数。第2列表示有两个数可以填充
    int mod=1000000007;
    int i=1,j=0,m=0;                      //关于数组(i,j),i个数,j个值.第i个为max,(i-1,j)种。为max-1，有（i-1，j-1）种。为max-2，有（i-1，j-2）种。直至（i-1，1）手工写下这个数组，会发现如19行表示。
    for(j=0;j<k;j++){f[0][j]=i;i++;}               //第一行赋值为1，2，3，4，5，6.。。
    for(i=1;i<aLen;i++){f[i][0]=1;}                  //第一列赋值为1，1，1，1，1，
    for(i=1;i<aLen;i++){                              //根据输入的参数，确定可能会用到的f[i][j];
        for(j=1;j<k;j++){
            f[i][j]=(f[i-1][j]+f[i][j-1])%mod;            //mod防止溢出
        }
    }
    printf("%ld %ld",f[1][4],f[aLen-1][k-1]);
    int r=0,l=0,l1=0,l2=0,num=1,flag=0;
    for(i=0;i<aLen;i++){                          //外层循环判断数组里的树，主要为了找零
        flag=0;
        j=i;
        while(a[j]==0&&j<aLen){                   //为了找连续为零的个数
            j++;
            flag=1;                                  //跳出while的时候，j是连续零后面的序号
        }
        if(flag==1){                               //有零就找
            if(i==0){                               //l为了确定前面数组里的列（值的个数），
               l1=1;
            }else{
               l1=a[i-1];                            //值的下限，注意，下限最小为1
             }

            if(j==aLen){
               l2=k;
            }
            else{
                l2=a[j];                          //值的上限，
            }
            l=l2-l1;                                //值
            r=j-i-1;                                //填充个数
            num=(num*f[r][l])%mod;                   //mod防止溢出
        }
        i=j;
    }
    return num;
}