寫在前面：因為之前沒寫的C++的USACO Training的解題報告太多……所以就不寫了，要是想要代碼可以聯系我：xiedong_1993@foxmail.com

這題就是傳說中的五維背包，其實寫起來難度不大。但是我寫的時候可以說是遇到了重重困難。因為我對C++的掌握還不如Pascal，所以很多東西寫的不是很熟。這題有一個很大的問題就在于，最后有用的只有五種物品，但是物品的編號卻又很多。處理的方法有幾種，一種是離散化，但是這個太SB了。。為了處理這么弱的數據還要排序重標號實在得不償失。另一種是直接就標號，但是面臨的問題就是，需要用的五種標號在能標之前就要被用到，就涉及到了一個問題，如何略過前面的部分，先處理后面的。。

兩種方案：1、全讀到一個數組里面，然后再將這個數組重新處理。這個方法可以是可以，但是浪費時間也浪費空間。

?????????????????? 2、先直接不讀前面的部分，讀后面的，然后關文件，再開一遍，把前面的讀進來。我這里用的就是后者。

我們知道pascal處理這個問題很簡答，只要reset一下就好。但是C++需要先關閉文件，再全部重新關聯一遍。因此學會了fclose……fclose之后重新freopen就好了。

還有更悲劇的，pascal中跳過一樣直接readln就好，但是C++貌似讀個回車是不好使的。。。還得挨個字符跳，不知有沒有好的其他的方法……

我的方法：

for (int i = 0; i < m; i++) {char ch = '\0';while (ch != '\n') scanf("%c", &ch); }

這兩個問題處理了之后依舊卡了很長時間，很簡單……遇到一個USACO的exit code，我最開始覺得可能是那塊的庫他沒有，但是后來發現是超內存了。。。（注意：以后如果在USACO遇到exit code 127就是超內存了）剩下的DP就簡單了，dp[i1][i2][i3][i4][i5]就是五樣東西各這些個的時候需要的最少花費。

代碼：

/* TASK:shopping LANG:C++ */ #include <iostream> #include <fstream> #include <climits> using namespace std;int n,m; int no[1200], cost[120]; int need[6]; int data[120][6]; int dp[14][14][14][14][14]; const int inf = INT_MAX;void init() {scanf("%d\n", &m);for (int i = 0; i < m; i++){char ch = '\0';while (ch != '\n') scanf("%c", &ch);}scanf("%d", &n);for (int i = 0; i < 120; i++) no[i] = -1;for (int i = 0; i < n; i++){int x,y,w;scanf("%d%d%d", &x, &y, &w);no[x] = i; need[i] = y;cost[m + i] = w; data[m + i][i] = 1;}fclose(stdin);freopen("shopping.in", "r", stdin);scanf("%d", &m);for (int i = 0; i < m; i++){int num;scanf("%d", &num);for (int j = 0; j < num; j++){int x,y;scanf("%d%d", &x, &y);if (no[x] != -1)data[i][no[x]] += y;}scanf("%d", &cost[i]);}m += n;for (int i1 = 0; i1 <= need[0]; i1++)for (int i2 = 0; i2 <= need[1]; i2++)for (int i3 = 0; i3 <= need[2]; i3++)for (int i4 = 0; i4 <= need[3]; i4++)for (int i5 = 0; i5 <= need[4]; i5++)dp[i1][i2][i3][i4][i5] = inf; }void solve() {dp[0][0][0][0][0] = 0;for (int i1 = 0; i1 <= need[0]; i1++)for (int i2 = 0; i2 <= need[1]; i2++)for (int i3 = 0; i3 <= need[2]; i3++)for (int i4 = 0; i4 <= need[3]; i4++)for (int i5 = 0; i5 <= need[4]; i5++)if (dp[i1][i2][i3][i4][i5] < inf)for (int i = 0; i < m; i++){int t1 = i1 + data[i][0];int t2 = i2 + data[i][1];int t3 = i3 + data[i][2];int t4 = i4 + data[i][3];int t5 = i5 + data[i][4];dp[t1][t2][t3][t4][t5] = min(dp[t1][t2][t3][t4][t5], dp[i1][i2][i3][i4][i5] + cost[i]);} }void print() {printf("%d\n", dp[need[0]][need[1]][need[2]][need[3]][need[4]]); }int main() {freopen("shopping.in", "r", stdin);freopen("shopping.out", "w", stdout);init();solve();print();return 0; }

轉載于:https://www.cnblogs.com/Skyprophet/archive/2011/05/23/2054698.html

總結

以上是生活随笔為你收集整理的USACO 3.3.2 Shopping Offers解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。