| Projects |
| Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB |
| Total submit users: 20, Accepted users: 18 |
| Problem 11015 : No special judgement |
| Problem description |
| In a certain week, a company wants to finish m projects. To this end, the company can employ at most n people from the unemployment agency for a period of one week. Each external employee will cost the company salary euro, unless the project in which he/she is involved is not completed in time. In that case no payment is due. For each project the company knows from experience the probability that the project will be completed within a week, as a function of the number of employees working on it. These probabilities are given as percentages pij, where i (with 1 <= i <= m) is the number of the project and j is the number of people working on it. Of course, when nobody is working on a project i, the probability pi0 is zero percent. If project i is indeed finished within a week, the company earns reward(s) euro; if it is not ready in time, the company has to pay a fine of punishment(i) euro. Of course the company wants to maximize its total expected profit① at the end of the week by finding the optimal number of external employees to hire, and how to divide them over the projects. The optimal number of employees is the total number of people needed to achieve the maximal expected profit. Your task in this matter is to calculate this optimal number of external employees. Remember that at most n people are available. Furthermore: if a person is employed, he / she works on one and only one project. |
| Input |
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
One line with one integer m with 1 <= m <= 100: the number of projects.
One line with one integer n with 0 <= n <= 100: the maximal number of available employees.
One line with one integer salary with 0 <= salary <= 1,000: the salary of one employee. Remember that the salary is given in euros.
m lines, each line corresponding to a project i, containing n integers pi1, pi2, ……, pin (the percentages, with 0 <= pi1, pi2, ……, pin <= 100), followed by two integers corresponding to the reward and the punishment for project i. All values are separated by single spaces. Both reward and punishment are given in euros and are between 0 and 100,000(boundaries included). |
| Output |
| For every test case in the input file, the output should contain two lines. The first line contains the maximal expected profit in eurocents. The second line contains the total number of external employees that must be hired in order to achieve this maximal expected profit. If the maximal expected profit can be achieved by different (total) numbers of employees, then these different numbers must be given in increasing order. Numbers have to be separated by single spaces. ①Let p (0 <= p <= 1) be the probability that a job is finished in time, and let E1 be the profit in that case. Furthermore, let E2 be the (negative) profit in case the job is not finished in time. Then the expected profit for this particular job is p * E1 + (1 - p) * E2. |
| Sample Input |
3
1
4
200
90 100 100 100 2000 0
2
2
100
80 80 2100 500
0 100 1700 500
3
4
100
100 80 80 70 1000 100
100 90 80 90 500 50
100 70 60 50 700 100
|
| Sample Output |
162000
1
100000
1 2
190000
3
|
动态规划，注意边界的初始化，g[i][j]表示 j 个人完成 i 项工作最大利润。注意初始化的时候 g[ i ][ 0] =sum f[k] (1<=k<=m) g[0][i]=-inf (1<=i<=n)
g[0][0]=0; 其他的 g[i][j]=-inf;
然后状态转移方程
g[i][j]=max(g[i-1][k]+(reward[i]-salary*(j-k))*f[i][j-k]/100-(100-f[i][j-k])*fine[i]/100,g[i][j])
#include <iostream>
#include <iomanip>
#define inf 1e16;
using namespace std;
double g[200][200];
int f[200][200];
int n,m,salary;
int reward[200],fine[200];
int max(int x,int y)
{
if (x>y) return x;
else
return y;
}
int main()
{
int t,i,j,k;
cin>>t;
memset(f,0,sizeof(f));
while (t--)
{
cin>>n>>m;
for (i=0;i<=n;i++)
for (j=0;j<=m;j++)
g[i][j]=-inf;
g[0][0]=0;
cin>>salary;
salary*=100;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++)
cin>>f[i][j];
cin>>reward[i];
reward[i]*=100;
cin>>fine[i];
fine[i]*=100;
g[i][0]=g[i-1][0]-fine[i];
}
for (i=1;i<=m;i++)
g[0][i]=-salary*i;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
for (k=0;k<=j;k++)
g[i][j]=max(g[i-1][k]+(reward[i]-salary*(j-k))*f[i][j-k]/100-(100-f[i][j-k])*fine[i]/100,g[i][j]);
double mm=-inf;
for (i=0;i<=m;i++)
if (g[n][i]>mm) mm=g[n][i];
int num=0;
int ans[200];
for (i=0;i<=m;i++)
if (g[n][i]==mm)
{
ans[num]=i;
num++;
}
cout<<setiosflags(ios::fixed)<<setprecision(0);
cout<<mm<<endl;
for (i=0;i<num;i++)
{
cout<<ans[i];
if (i<num-1) cout<<' ';
}
cout<<endl;
}
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。