hdu1171

题意:有 $n$ 种设施,每种有价值 $v_i$ 和数量 $m_i$,求一种方案使得分成价值尽可能相近的两组。($n \leq 50, v_i \leq 50, m_i \leq 100$)

分析:

可以用背包做,这里讲母函数的做法。

直接用样例说明一下:

3
10 1
20 2
30 1

其母函数为 

$$(1+x^{10})(1+x^{20}+x^{40})(1+x^{30})$$

多项式展开后,倒着枚举 $i$ 从 $sum/2$ 到0,如果 $x^i$ 前的系数不为0说明能够组成 $i$,则答案为 $sum-i, i$.

#include<bits/stdc++.h>
using namespace std;

const int maxn =  50+5;
int c1[250000+10], c2[250000+10];    //c1存放前面项计算出来的结果,c2存放中间结果
int n;
int value[maxn], amount[maxn];

int main()
{
    while(scanf("%d", &n) == 1 && n >= 0)  //负数结束,不一定是-1。。。
    {
        int sum = 0;
        for(int i = 1;i <= n;i++)
        {
            scanf("%d%d", &value[i], &amount[i]);
            sum += value[i]*amount[i];
        }

        for(int i=0; i<=sum/2; ++i)  c1[i] = c2[i] = 0;
        for(int i = 0;i <= value[1]*amount[1]; i+= value[1])  c1[i] = 1;
        for(int i=2; i<=n; ++i)   // n个大括号
        {

            for(int j=0; j<=sum/2; ++j)   // 枚举c1中的项
                for(int k=0; k<=value[i]*amount[i] && j+k<=sum/2; k+=value[i])  // 枚举第i个大括号中的项
                {
                    c2[j+k] += c1[j];
                }
            for(int j=0; j<=sum/2; ++j)     //转移到c1
            {
                c1[j] = c2[j];
                c2[j] = 0;
            }
        }


        for(int i = sum/2;i >= 0;i--)
            if(c1[i] != 0)
            {
                printf("%d %d\n", sum-i, i);
                break;
            }
    }
    return 0;
}
View Code

p2000拯救世界

题目:给出10个限制,求组成n的方案数

分析:每个限制都可以写成一个母函数,由于每个限制是独立的,直接乘起来,结果为 $\displaystyle \frac{1}{(1-x)^5}$

有结论:$\displaystyle \frac{1}{(1-x)^k} = \sum_{i=0}^{\infty}C_{k+i-1}^i\cdot x^i$(用广义二项式定理证)

所以有 $\frac{1}{(1-x)^5}$ 的 $n$ 项的系数为 $C_n^4$.

//因为这题卡常,所以python过不了,然后用pypy就过了

n=int(input())
print((n+1)*(n+2)*(n+3)*(n+4)//24)
View Code

参考链接:

1. http://www.acmsearch.com/article/show/5079

2. http://www.wutianqi.com/blog/594.html

3. https://www.luogu.org/problemnew/solution/P2000

01-18 23:31