题意:

N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张宽为A长为B的白纸上。这些长方形被放置时，保证了它们的边与白纸的边缘平行。所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。

分析:

 这题卡了很长时间，因为只想到最直接的办法，用boolean数组记录，从后往前覆盖，最后扫描一遍

 但长方形的长宽很大（<=10,000），很容易超时

 然后同学告诉我用矩形分割来做

 +--------+      +-+--+--+
 |        |      | |2 |  |
 |        |      + +--+  |
 |  +-+   |  --> | |  |  |
 |  +-+   |      |1|  |3 |
 |        |  

题意:给n个数从中选出一组数使其和为这N个数之和减去给定的TotalW

     1)没有方案输出0

     2)有多种方案输出-1

     3)只有一种方案，按升序输出这组数的编号

分析：拿到题很快就想到类似于DP的算法求出最后的方案数

      f[j]:=f[j]+f[j-a[i]]

      {f[j]--总和为j的方案数，a[i]--编号为i的数的大小

      对于每个大于等于a[i]的总和情况，考虑最后一个数是a[i]的情况}

      算的时候遇到问题

       for i:=a[i] to max do

        if f[j-a[i]]<>0 then inc(f[j],f[j-a[i]]);

     这样的话可能a[i]<j-a[i]，f[j-a[i]]可能已经是最后由a[i]结尾的情况

     f[j]不能由f[j-a[j]]的最后加上a[i]得到

     所以考虑从

利用积性函数的优化.

这个文章主要介绍了3算法

1线性时间筛素数

2线性时间求前n个数的欧拉函数值

3线性时间求前n个数的约数个数

一、   首先介绍下积性函数。

下面是wiki的条目：

在非数论的领域，积性函数指有对于任何a,b都有性质f(ab)=f(a)f(b)的函数。

在数论中的积性函数。对于正整数n的一个算术函数f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)f(b)，在数论上就称它为积性函数。

若某算术函数f(n)符合f(1)=1，且就算a,b不互质，f(ab)=f(a)f(b)，称它为完全积性的。

例子

φ(n) －欧拉φ函数，计算与n互质的正整数之数目

μ(n) －默比乌斯函数，关于非平方数的质因子数目

【大意】有几种题目,每一种有无限道,给出做各种题的时间和得分,求在给定的时间内可以得到的分数最大值

【算法】无限背包,但朴素的无限背包超时 ,需要优化一下,再读入的过程中就进行DP

【程序清单】

 {ID:wangyang91
 PROG:inflate
 LANG:PASCAL
}var f:array[0..10000]of longint;
    n,i,j,k,t,m:longint;

begin
 assign(input,'inflate.in');reset(input);
 assign(output,'inflate.out');rewrite(output);

 readln(m,n);
 for i:=1 to n do
  begin
   readln(k,t);
   for j:=0 to m-t do
    if f[j+t]<f[j]+k then
     f[j+t]:=f[j]+k;
  end;
 writeln(f[m]);

 close(input);
 close(output);
end.