PRoblem
Mary likes playing with rubber bands. It’s her birthday today, and you have gone to the rubber band shop to buy her a gift.
There are N rubber bands available in the shop. The i-th of these bands can be stretched to have any length in the range [Ai, Bi], inclusive. Two rubber bands of range [a, b] and [c, d] can be connected to form one rubber band that can have any length in the range [a+c, b+d]. These new rubber bands can themselves be connected to other rubber bands, and so on.
You want to give Mary a rubber band that can be stretched to a length of exactly L. This can be either a single rubber band or a combination of rubber bands. You have M dollars available. What is the smallest amount you can spend? If it is impossible to accomplish your goal, output IMPOSSIBLE instead.
Limits
1 ≤ T ≤ 100. 1 ≤ Pi ≤ M. 1 ≤ L ≤ 10000. 1 ≤ Ai ≤ Bi ≤ 10000. Small dataset
1 ≤ N ≤ 10. 1 ≤ M ≤ 100. Large dataset
1 ≤ N ≤ 1000. 1 ≤ M ≤ 1000000000.
分析：
小数据应该可以通过暴力解决，对所有的N个rubber bands，枚举出所有2^N种子集，并判断每种组合是否满足长度要求，并选取其中最小花费即可。但对于大数据来说 2^N太大了。选用动态规划来解决, 这边也参考了scoreboard上前几位作者的代码。动态规划：
设数组dp[L+1]，其中dp[i]表示要达到长度为i的rubber band所需最少花费。对每个rubber band按顺序考虑到数组dp中去，即首先考虑只有前1个band时dp的状态，再考虑只有前2个band时dp的状态，……，最后考虑前N个band时的dp状态，考察dp[L]是否小于预算M即可。初始时将所以dp元素设为MAX， dp[0]=0当考虑第i个rubber band进入dp数组时，因为其拉伸长度可以达到[Ai,Bi], 所以对dp[j]来说，只需取dp数组中下标为j-Bi到j-Ai这一段中最小值+Pi 来决定是否更新当前dp[j]。（注意j-Bi到j-Ai不要越界）当第i个rubber band进入考虑范围时，按上述更新一遍dp数组即可。但是, 对每个j查找“dp数组中下标为j-Bi到j-Ai这一段中最小值”很耗时，考虑到其实是一个滑动窗口中的最小值，可借鉴leetcode239减少复杂度。 但一开始用deque实现比较耗时，后来直接用数组实现就变快了。
代码:Github
#include <iostream>#include <math.h>#include <vector>#include <algorithm>#include <deque>using namespace std;typedef long long ll;int T;int main() { FILE *fin, *fout; fin=fopen("D-large-practice.in", "r"); fout = fopen("output", "w"); fscanf(fin, "%d", &T); for (int kk = 1; kk <= T; kk++) { int num, money, length; fscanf(fin, "%d %d %d", &num, &money, &length); vector<ll> dp(length + 1, INT_MAX); dp[0] = 0; for (ll i = 0; i < num; i++) { int a, b; int p; fscanf(fin, "%d %d %d", &a, &b, &p); //寻找长度为b-a+1的sliding window中最小值的下标 记录到que中 vector<int> que(length + 1, 0); int start = 0; int end = 0; for (int k = a; k < b&&length - k >= 0; k++) { while (end > start && dp[que[end - 1]] >= dp[length - k]) end--; que[end++] = length - k; } for (ll j = length; j >= 0; j--) { if (j - b >= 0) { while (end > start && dp[que[end - 1]] >= dp[j - b]) end--; que[end++] = j - b; } if (start < end) dp[j] = min(dp[j], dp[que[start]] + p); if (dp[start] >= j - a) start++; } } if (dp[length] <= money) fprintf(fout, "Case #%d: %d/n", kk, dp[length]); else fprintf(fout, "Case #%d: IMPOSSIBLE/n", kk); } }
