[UVA][dp] 10086 - Test the Rods
Problem B
Test the Rods
Input: standard input
Output: standard output
National Construction and Project Centre (NCPC) and the Bureau of Civil Engineering Works (BCEW) have been given the authority of testing and certifying the quality of rods used in construction works in the country. The Get and Do construction company has recently got a contract of construction at different sites of the country. Before the construction can start they want to get the rods from their n sites tested either at NCPC or at BCEW. Get and Do has got the permission of testing T1 rods at NCPC and T2 at BCEW. There are mi samples at site i (1 <= i <= n). Sum total of these samples over all the n sites is just equal to (T1 + T2). The cost of testing j items from site i at NCPC is Ci,j,1 and that of testing at BCEW is Ci,j,2. Write a program to find a minimum cost testing schedule for the Get and Do company.
Input
The input may contain multiple test cases. The first line of each test case contains the two nonnegative integers T1 and T2 (1 <= T1 + T2 <= 300). The next line contains n (1 <= n <= 30). Then follow 3n lines. For 1 <= i <= n, line (3i - 2) contains the value of mi (1 <= mi <= 20), line (3i - 1) contains mi nonnegative integers Ci,j,1 (1 <= j <= mi) and line 3i contains mi nonnegative integers Ci,j,2 (1 <= j <= mi). You may assume that 0 <= Ci,j,1, Ci,j,2 <= 1000.
A test case containing two zeros for T1 and T2 terminates the input, and this case must not be processed.
Output
For each test case in the input print two lines. The first line contains an integer giving the minimum cost for testing all the samples at NCPC and BCEW. The next line contains n integers with two consecutive integers separated by a single space. The i-th integer gives the numbers of samples from site i that are tested at NCPC (it is implicit that the rest are tested at BCEW). Note that the second output line is not unique, and hence any optimal testing schedule is acceptable. Print a blank line after the outputs of each test case.
Sample Input
10 125
5
10 30 70 150 310
10 20 40 60 180
7
30 60 90 120 160 200 240
20 60 100 130 160 200 240
4
40 60 80 100
30 70 100 120
3
60 120 180
20 50 90
3
30 70 100
30 70 100
0 0
Sample Output
5801 3 4 0 2
_________________________________________________________________________________________
Rezaul Alam Chowdhury
"Two things are infinite. One is the universe, the other is human stupidity and I am not sure about the former."
題目描述：
給定兩家公司，分別指派 T1, T2 個檢測樣品的個數，而在每一站中，會有 m 個樣品，而兩家公司有不同的表格，對應假使檢測 j 個樣品的價錢(不是第 j 個樣品的價錢)，問兩公司分配後的總花費最小為何。
保證樣品總數 = T1+T2，最後輸出 NCPC 在每一站的分配樣品數。
最小花費一定只有一解，但是分配的個數任何一組解都可以。
題目解法：
解法有兩種，一種是 dp[i][j] 分別表示 NCPC 檢測 i 個樣品，BCEW 檢測 j 個樣品。
或者使用 dp[i] 表示 NCPC 檢測 i 個樣品。
由於不是 NCPC 檢測，就是 BCEW 檢測，所以不會有影響。
轉移方法就很簡單了，窮舉每一站的分配個數。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[305][305];
int argdp[305][305][2];
int main() {
int T1, T2;
int n, m;
int A[305], B[305];
int i, j, k;
while(scanf("%d %d", &T1, &T2) == 2) {
if(T1 == 0 && T2 == 0)
break;
memset(dp, 31, sizeof(dp));
dp[0][0] = 0;
scanf("%d", &n);
int ch = 0;
for(i = 0; i < n; i++) {
scanf("%d", &m);
for(j = 1; j <= m; j++)
scanf("%d", &A[j]);
for(j = 1; j <= m; j++)
scanf("%d", &B[j]);
A[0] = B[0] = 0;
for(j = 0; j <= m; j++) {
for(k = 0; k <= ch; k++) {
if(k+j <= T1 && (ch+m)-(k+j) <= T2) {
if(dp[k+j][(ch+m)-(k+j)] > dp[k][ch-k]+A[j]+B[m-j]) {
dp[k+j][(ch+m)-(k+j)] = dp[k][ch-k]+A[j]+B[m-j];
argdp[k+j][(ch+m)-(k+j)][0] = k;
argdp[k+j][(ch+m)-(k+j)][1] = ch-k;
}
}
}
}
ch += m;
}
printf("%d\n", dp[T1][T2]);
int ret[105];
for(i = n-1; i >= 0; i--) {
ret[i] = T1-argdp[T1][T2][0];
int tt1 = T1, tt2 = T2;
T1 = argdp[tt1][tt2][0];
T2 = argdp[tt1][tt2][1];
}
for(i = 0; i < n; i++) {
if(i) putchar(' ');
printf("%d", ret[i]);
}
puts("\n");
}
return 0;
}