zoj 1013 Great Equipment DP

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=13

很经典的一个DP的题目

定义dp[i][num1][num2]表示前i个车装num1个装备1和num2个装备2之后最多能装的装备3的个数

那么dp[i][p+x][q+y]=max(dp[i][p+x][q+y],dp[i-1][p][q]+num(x,y));

其中num(x,y)表示第i辆车装x个装备1和y个装备2后还能最多装的装备3的个数

x,y的范围即为第辆车的可以装的装备1和装备2的最大个数

可以看出dp[i]只与dp[i-1]有关，要用滚动数组，否则会超内存

代码：

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#define maxn 550

#define maxn_1 110

using namespace std;

int dp[][maxn][maxn];

int w[maxn_1];

int s[maxn_1];

int w1,s1,d1;

int w2,s2,d2;

int w3,s3,d3;

int c1,c2,c3,d4;

int prev,now;

int put(int num,int p,int q)

{

      int nw=(w[num]-p*w1-q*w2)/w3;

      int ns=(s[num]-p*s1-q*s2)/s3;

     return min(nw,ns);

}

int main()

{

    int n;

    int icase=;

    while(scanf("%d",&n) != EOF&& n)

    {

        scanf("%d%d%d",&w1,&s1,&d1);

        scanf("%d%d%d",&w2,&s2,&d2);

        scanf("%d%d%d",&w3,&s3,&d3);

        scanf("%d%d%d",&c1,&c2,&c3);

        scanf("%d",&d4);

       for(int i=;i<=n;i++)

        scanf("%d%d",&w[i],&s[i]);

        memset(dp[],,sizeof(dp[]));

        int max_1=;

        int max_2=;

        prev=,now=;

        for(int i=;i<=n;i++)

          {

              memset(dp[now],-,sizeof(dp[now]));

             int num1=min(w[i]/w1,s[i]/s1);

             int tmp;

             for(int p=;p<=num1;p++)

               {

                  int num2=min((w[i]-p*w1)/w2,(s[i]-p*s1)/s2);

                  if(p==) tmp=num2;

                  for(int q=;q<=num2;q++)

                  {

                      int nn=put(i,p,q);

                    for(int k1=;k1<=max_1;k1++)

                       for(int k2=;k2<=max_2;k2++)

                      {

                        if(dp[prev][k1][k2]!=-)

                         dp[now][k1+p][k2+q]=max(dp[now][k1+p][k2+q],dp[prev][k1][k2]+nn);

                      }

                  }

               }

             max_1+=num1;

             max_2+=tmp;

             swap(now,prev);

         }

       int ans=;

       for(int i=;i<=max_1;i++)

         for(int j=;j<=max_2;j++)

           {

             if(dp[prev][i][j]!=-)

             {

               int  num_4=min(min(i/c1,j/c2),dp[prev][i][j]/c3);

               ans=max(max(ans,i*d1+j*d2+dp[prev][i][j]*d3),(i-num_4*c1)*d1+(j-num_4*c2)*d2+(dp[prev][i][j]-num_4*c3)*d3 +num_4*d4);

             }

           }

       if(icase++) cout<<endl;

       cout<<"Case "<<icase<<": "<<ans<<endl;

    }

    return ;

}

巴特西

zoj 1013 Great Equipment DP

最新文章

热门文章