1152 空运物资（母函数）(第七届河南省程序设计大赛)

冷不防 2021-09-26 15:22 238阅读 0赞

题目：

## 问题 : 空运物资 ##

时间限制： 1000 ms  |  内存限制： 65535 KB

难度： 2

## 题目描述 ##

在灾区，多数人已经受伤，缺水，少食物，精神处在崩溃的边缘。很多人的生存条件仅能维持几天。  
现在已知四种打包过的急需物品重量分别为C1, C2, C3,C4 ，数量分别为M1，M2，M3，M4包。一架运输机的载重量为W, 现在各部队关心将一架运输机装满共有多少种运载方案，以便调度进行空运。  
比如C=\{ 100, 200, 500, 1000\}, M=\{ 3, 2, 3, 1 \}, W=1000, 一共有4种运载方案:  
1000=100+100+100+200+500  
1000=100+200+200+500  
1000=500+500  
1000=1000

## 输入 ##

第一行： C1 C2 C3 C4 N    其中N为空运的部队数  
接下来n行： Mi1 Mi2 Mi3 Mi4 Wi    表示各运载部队需空运的4种物品数量Mi和各自运输机的载重量Wi i=1,2,….. , N

## 输出 ##

输出有N行，表示各部队运载物品的方案总数，保证答案在10000范围内

【约束条件】  
（1）0< Cj <= 1000 0 <= Mij <= 500 i =1,2,….. , N j =1,2,3,4  
（2）N<=1000 0 < Wi <= 100000 i =1,2,….. , N  
（3）时间限制： 1000MS

## 样例输入 ##

1 2 5 10 2
    3 2 3 1 10
    1000 2 2 2 900

## 样例输出 ##

4
    27

题目描述：

用母函数解的，母函数的学习可以点击这篇博客：[http://www.cnblogs.com/tanky\_woo/archive/2010/08/02/1790540.html][http_www.cnblogs.com_tanky_woo_archive_2010_08_02_1790540.html]讲解的很详细。

有四种物资，每种物资都可以用一个表达式来表达，然后累乘就可以了。

代码：

#include<stdio.h>
    #include<string.h>
    int main()
    {
        int d,w;    //代表总部队数和每个部队的装载量
        int i,j,k,l;
        int a[5],m[5];    //表示四种物资的质量和数量
        int c[10010],e[10010];    //存累乘的表达式的系数和中间结果系数，第i个值表示为x^i的系数
        while(scanf("%d%d%d%d%d",&a[1],&a[2],&a[3],&a[4],&d)!=EOF){
            for(i = 0;i < d;i++){
                scanf("%d%d%d%d%d",&m[1],&m[2],&m[3],&m[4],&w);
                memset(e,0,sizeof(e));
                memset(c,0,sizeof(c));
                int ij;
                for(ij = 0,j = 0;j<=w&&ij<=m[1];j+=a[1],ij++)    //初始化第一个表达式的系数，下面也用数组c来存累乘的表达式的系数
                    c[j] = 1;
                for(j = 2;j<=4;j++){    //需要相乘的表达式个数
                    for(k = 0;k<=w;k++){    //这重循环表示的是数组c的下标，因为最大装载量为w，所以系数只需存到w就可以了
                        for(l = 0;l + k<=w&&l/a[j]<=m[j];l+=a[j]){    //这重循环表示的是将要累乘到数组c的表达式，l的每次增量为a[j]，不懂的仔细想想，可以再看看那篇博客。
                            e[l+k] +=c[k];
                        }
                    }
                    for(k = 0;k<=w;k++){    //将结果保存到数组c
                        c[k] = e[k];
                        e[k] = 0;
                    }
                }
                printf("%d\n",c[w]);
            }
        }
        return 0;
    }

[http_www.cnblogs.com_tanky_woo_archive_2010_08_02_1790540.html]: http://www.cnblogs.com/tanky_woo/archive/2010/08/02/1790540.html