Ant Counting　(PKU 3046)

PKU Online Judge

http://acm.pku.edu.cn/JudgeOnline/problem?id=3046

問題

T種類の数値がそれぞれNi個存在する。それらの数値を使って大きさS〜Bの集合を作りたい。何種類の集合の作り方が存在するか？
1<=T<=1000
1<=Ni<=100

解法

DPで解く。
DP[i][j]はi種類目の数値までを使って大きさjの集合を作る方法の数を表す。このDPの要素は尺取メソッドを使えば平均O(1)で更新できるので全体としてはO(TB)で解ける。
実際にはメモリが足りないのでDP[2][B]としてメモリを使いまわす。