2014年1月31日

UVa 10086 - Test the Rods

```#include <cstdio>

int main() {
int T1 ,T2;
while (scanf("%d%d", &T1, &T2) && (T1 + T2)) {
int n;
scanf("%d", &n);
int num[31], cost[2][31][21];
for (int i = 1; i <= n; i++) {
scanf("%d", num + i);
cost[0][i][0] = cost[1][i][0] = 0;
for (int j = 1; j <= num[i]; j++) {
scanf("%d", &cost[0][i][j]);
}
for (int j = 1; j <= num[i]; j++) {
scanf("%d", &cost[1][i][j]);
}
}
int sum = 0, dp[31][301], pick[31][301];
for (int i = 0; i <= n; i++) {
for (int t1 = 0; t1 <= T1; t1++) {
dp[i][t1] = 1e8;
}
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
sum += num[i];
for (int use = num[i]; use >= 0; use--) {
for (int t1 = sum < T1 ? sum : T1; t1 >= use; t1--) {
int value = dp[i - 1][t1 - use] + cost[0][i][use] + cost[1][i][num[i] - use];
if (value < dp[i][t1]) {
dp[i][t1] = value;
pick[i][t1] = use;
}
}
}
}
printf("%d\n", dp[n][T1]);
int i = n, t1 = T1, ans[31];
while (i) {
ans[i] = pick[i][t1];
t1 -= ans[i];
i--;
}
for (int i = 1; i <= n; i++) {
printf("%d%s", ans[i], i == n ? "\n\n" : " ");
}
}
return 0;
}
```