pku3459 Projects (动态规划)

题目：

题目大意是说n个人做m项工程，然后给出工人的薪水，和工程按期完工的概率，以及按时完工的酬劳和未按时完工的罚款，要求出最大利润。。需要注意的是，薪水输出的是欧元为单位，输出的是以分为单位。。本题是一个简单的DP，但仍是耗了几个小时，主要是题目一直没看太懂，不知道那个测试数据咋来的。。写完后而且有BUG，WA了好多次才过。。真弱哇。。。BS下。。。

状态方程：f[i+1][j]=max(f[i][k]+d[i+1][j-k]);(0<=k<=j)

f[i][j]:前i个工程，雇j个人可以达到的最大利润。

d[i][j]:第i个工程，雇j个人可得到的利润。(j个人全部用上)

我的代码：

 

#include<iostream>
using namespace std;

const int inf=-1000000000;
int max(int a,int b)
{return a>b?a:b;}

int main()
{
    int test,n,m,i,j,k,salary,MAX,flag,reward[101],punishment[101];
    int f[101][101],d[101][101],p[101][101];
    cin>>test;
    while(test--)
    {
        cin>>m>>n>>salary;    
        for(i=0;i<m;i++)
        {
            p[i][0]=0;
            for(j=1;j<=n;j++)
                cin>>p[i][j];
            cin>>reward[i]>>punishment[i];
        }
        for(i=0;i<=m;i++)
            for(j=0;j<=n;j++)
                f[i][j]=inf;

        f[0][0]=0;
        for(i=0;i<m;i++)//很诡异，我开始写成从1到m的循环，就错了。。
            for(j=0;j<=n;j++)
            {
                MAX=inf;
                for(k=0;k<=j;k++)
                {
                    d[i+1][j-k]=(reward[i]-(j-k)*salary)*p[i][j-k]-punishment[i]*(100-p[i][j-k]);
                    if(f[i][k]+d[i+1][j-k]>MAX)
                        MAX=f[i][k]+d[i+1][j-k];
                }
                f[i+1][j]=MAX;
            }
        MAX=inf;flag=0;
        for(i=0;i<=n;i++)
            if(MAX<f[m][i])
                MAX=f[m][i];
        cout<<MAX<<endl;
        for(i=0;i<=n;i++)
            if(f[m][i]==MAX)
            {
                if(!flag)
                {
                    cout<<i;
                    flag=1;
                }
                else
                    cout<<" "<<i;
            }
        cout<<endl;
    }
    return 0;
}