题意：
一个套餐需要a个A，b个B，c个C。
你生产一个A需要t1,一个B需要t2，一个C需要t3时间。
你有n台机器。每台每天工作timei时间。
一件物品只能在一个机器上生产。
求你一天最多能生产多少套餐。
每天ABC产量上限是100，n<=10
解：
这个DP的状态表示真是奇怪..
有一种做法是设f[i][j][k][l]表示前i台机器生产j个A，k个B，l个C的最大套餐数量。
被我的 1 1 1 2 2 2 3 3 2 1 卡掉了，输出1，答案是0
还有一种做法是设f[i][j][k][l]表示前i台机器生产j个A，k个B，l个C的所需最少时间。
这是zbtrs提供的。我还没思考。但是直觉上感觉很不对劲....
最后是我用的，f[i][j][k]表示前i台机器生产j个A，k个B时所能生产的最多C数量。
一开始预处理出最大套餐值和最大ABC值。
转移就是枚举这一台/之前的机器生产了多少A和B，然后计算出C来。
注意，一开始的时候可能会从f[0][x][y]之类的不存在的状态转移过来。
解决方案是赋值为-1，特判。初值是f[0][0][0] = 0
有几个剪枝：第一个是这条生产线不能生产更多的A和B了，这时要break
还有就是这个状态的C已经满了，此时不用继续枚举转移了，直接出转移(goto flag)。
然后就把很吓人的时间复杂度剪下去了。
1 #include2 #include 3 #include 4 #define say(a) printf(#a); printf(" = %d \n", a) 5 const int N = 110; 6 7 int f[12][N][N], time[N]; 8 int a, b, c; 9 int t1, t2, t3;10 11 int main() {12 int n;13 scanf("%d%d%d", &a, &b, &c);14 scanf("%d%d%d", &t1, &t2, &t3);15 scanf("%d", &n);16 int sum = 0, ans = 0;17 for(int i = 1; i <= n; i++) {18 scanf("%d", &time[i]);19 sum += time[i];20 }21 int lm = sum / (a * t1 + b * t2 + c * t3);22 int maxA = std::min(lm * a, 100);23 int maxB = std::min(lm * b, 100);24 int maxC = std::min(lm * c, 100);25 26 memset(f, -1, sizeof(f));27 f[0][0][0] = 0;28 for(int i = 1; i <= n; i++) {29 f[i][0][0] = 0;30 }31 for(int i = 1; i <= n; i++) {32 for(int j = maxA; j >= 0; j--) {33 for(int k = maxB; k >= 0; k--) {34 /// get f[i][j][k]35 for(int jj = j; jj >= 0; jj--) {36 for(int kk = k; kk >= 0; kk--) {37 if(time[i] < (j - jj) * t1 + (k - kk) * t2) {38 goto flag;39 }40 if(f[i - 1][jj][kk] == -1) {41 continue;42 }43 f[i][j][k] = std::max(f[i][j][k],44 f[i - 1][jj][kk] + (time[i] - (j - jj) * t1 - (k - kk) * t2) / t3);45 if(f[i][j][k] >= maxC) {46 goto flag;47 }48 }49 }50 flag:51 int now = std::min(j / a, k / b);52 now = std::min(now, f[i][j][k] / c);53 ans = std::max(ans, now);54 }55 }56 }57 58 printf("%d", ans);59 return 0;60 }
codevs的数据很弱。强数据在洛谷上。