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.
分析：
小數(shù)據(jù)應(yīng)該可以通過暴力解決，對所有的N個rubber bands，枚舉出所有2^N種子集，并判斷每種組合是否滿足長度要求，并選取其中最小花費(fèi)即可。但對于大數(shù)據(jù)來說 2^N太大了。選用動態(tài)規(guī)劃來解決, 這邊也參考了scoreboard上前幾位作者的代碼。動態(tài)規(guī)劃：
設(shè)數(shù)組dp[L+1]，其中dp[i]表示要達(dá)到長度為i的rubber band所需最少花費(fèi)。對每個rubber band按順序考慮到數(shù)組dp中去，即首先考慮只有前1個band時dp的狀態(tài)，再考慮只有前2個band時dp的狀態(tài)，……，最后考慮前N個band時的dp狀態(tài)，考察dp[L]是否小于預(yù)算M即可。初始時將所以dp元素設(shè)為MAX， dp[0]=0當(dāng)考慮第i個rubber band進(jìn)入dp數(shù)組時，因?yàn)槠淅扉L度可以達(dá)到[Ai,Bi], 所以對dp[j]來說，只需取dp數(shù)組中下標(biāo)為j-Bi到j(luò)-Ai這一段中最小值+Pi 來決定是否更新當(dāng)前dp[j]。（注意j-Bi到j(luò)-Ai不要越界）當(dāng)?shù)趇個rubber band進(jìn)入考慮范圍時，按上述更新一遍dp數(shù)組即可。但是, 對每個j查找“dp數(shù)組中下標(biāo)為j-Bi到j(luò)-Ai這一段中最小值”很耗時，考慮到其實(shí)是一個滑動窗口中的最小值，可借鑒leetcode239減少復(fù)雜度。 但一開始用deque實(shí)現(xiàn)比較耗時，后來直接用數(shù)組實(shí)現(xiàn)就變快了。
代碼: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中最小值的下標(biāo) 記錄到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); } }
