weijifen.rar_积分

#include <iostream> #include <iomanip> #include <vector> #include <algorithm> #include <functional> using namespace std; class BigNum { vector<int> val; public: static const int NUM = 10000; static const int WIDTH = 4; BigNum(int n = 0); friend ostream& operator << (ostream &out, const BigNum &n); bool operator != (const BigNum &n) const {return val != n.val;} BigNum& operator += (const BigNum &n2); }; BigNum::BigNum(int n /* = 0 */) { do // 保证val至少有一个元素 { int a = n / NUM; int b = n % NUM; val.push_back(b); n = a; } while(n > 0); } BigNum& BigNum::operator += (const BigNum &n2) { if (val.size() < n2.val.size()) // n2短 val.resize(n2.val.size()); transform(n2.val.begin(), n2.val.end(), val.begin(), val.begin(), plus<int>()); int lastAdd = 0; for (vector<int>::iterator it = val.begin(); it != val.end(); ++it) { *it += lastAdd; if (*it >= BigNum::NUM) { *it -= BigNum::NUM; lastAdd = 1; } else lastAdd = 0; } if (lastAdd == 1) val.push_back(1); return *this; } ostream& operator << (ostream &out, const BigNum &n) { if (n.val.size() == 1) // 只有一个数 return out << n.val[0]; out << n.val.back(); char c = out.fill('0'); for (vector<int>::const_reverse_iterator it = n.val.rbegin()+1; it != n.val.rend(); ++it) out << setw(BigNum::WIDTH) << *it; return out << setfill(c); } #if 1 // 记录表法 const int MAX_N = 20; const int MAX_S = 1000; int n, S; int a[MAX_N], b[MAX_N]; BigNum T[MAX_N][MAX_S + 1] = {{0}}; // 记录表 BigNum Cal(int day, int done, int min, int max) { int left = S - done; // 还有多少题要做 if (left < min || left > max) // 超出可能的做题范围 return 0; // 方案必不成功，部分方案数为0 if (day == n - 1) // 最后一天，方案必然可能 return 1; // 部分方案数为1，递归终止 if (T[day][done] != 0) // 已经计算过 return T[day][done]; BigNum total = 0; // 部分方案数 for (int t = a[day]; t <= b[day]; t++) // 枚举 total += Cal(day + 1, done + t, min-a[day], max-b[day]); // 递归计算 T[day][done] = total; // 记录下来 return total; } int main() { // 读入数据 cin >> n >> S; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; int min = 0, max = 0; // 最少和最多做题数量 for (int i = 0; i < n; i++) { min += a[i]; max += b[i]; } cout << Cal(0, 0, min, max) << endl; return 0; } #else // 动态规划算法 const int MAX_N = 20; const int MAX_S = 1000; int n, S; int a[MAX_N], b[MAX_N]; BigNum fa[MAX_N][MAX_S+1]; int main() { // 读入数据 cin >> n >> S; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; int leftMin = 0, leftMax = 0; // 还剩下的天中最少和最多做题数 for (int i = 0; i < n; i++) { leftMin += a[i]; leftMax += b[i]; } // 第0天 int realMin = a[0], realMax = b[0]; // 到当前天为止，最少和最多做题数 leftMin -= a[0]; leftMax -= b[0]; if (realMin < S - leftMax) realMin = S - leftMax; if (realMax > S - leftMin) realMax = S - leftMin; for (int t = realMin; t <= realMax; t++) fa[0][t] = 1; for (int day = 1; day < n; day++) { realMin += a[day]; realMax += b[day]; leftMin -= a[day]; leftMax -= b[day]; if (realMin < S - leftMax) realMin = S - leftMax; if (realMax > S - leftMin) realMax = S - leftMin; for (int tall = realMin; tall <= realMax; tall++) // 对于总题量 for (int t = a[day]; t <= b[day] && t <= tall; t++) fa[day][tall] += fa[day-1][tall-t]; // 累计之前的可能方案数 } cout << fa[n-1][S] << endl; return 0; } #endif