P1417 烹调方案

/*

W&T.

读错题目了啊啊啊啊啊啊.

(每种食材只能用一次QWQ)

把所有情况处理了出来背包DP.

*/

#include<iostream>

#include<cstdio>

#define MAXN 51

#define MAXM 100001

#define LL long long

using namespace std;

LL f[MAXM],n,t,a[MAXN],b[MAXN],c[MAXN],w[MAXN*MAXM],tot,v[MAXN*MAXM];

LL read(){

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

    return x*f;

}

void init(){

    t=read();n=read();

    for(int i=1;i<=n;i++)  a[i]=read();

    for(int i=1;i<=n;i++)  b[i]=read();

    for(int i=1;i<=n;i++)  c[i]=read();

}

void slove(){

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

      for(int j=1;j<=t;j++){

        w[++tot]=a[i]-j*b[i];

        v[tot]=c[i];

      }

}

void dp(){

    for(int i=1;i<=tot;i++)

        for(int j=t;j>=v[i];j--)

    {

          f[j]=max(f[j],f[j-v[i]]+w[i]);

        printf("%d ",f[j]);

    }

    printf("%d",f[t]);

}

int main(){

    init();

    slove();

    dp();

    return 0;

}

/*

DP+贪心.

(国王游戏类似).

可以考虑有两个菜的三值分别为a1,b1,c1,a2,b2,c2

则两种情况为a1-(t+c1)*b1+a2-(t+c1+c2)*b2  （1）

　　　　　　 a2-(t+c2)*b2+a1-(t+c1+c2)*b1 （2）

如果（1）>（2）则化简得c1*b2<c2*b1.

按照这个条件排序之后跑一边01背包.

*/

#include<iostream>

#include<cstdio>

#define MAXN 51

#define LL long long

#define MAXM 100001

using namespace std;

LL f[MAXM],n,t,a[MAXN],b[MAXN],c[MAXN],w[MAXN*MAXM],tot,v[MAXN*MAXM];

LL read(){

    LL x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();

    return x*f;

}

void init(){

    t=read();n=read();

    for(int i=1;i<=n;i++)  a[i]=read();

    for(int i=1;i<=n;i++)  b[i]=read();

    for(int i=1;i<=n;i++)  c[i]=read();

}

void slove(){

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

      for(int j=i+1;j<=n;j++){

        if(b[i]*c[j]<b[j]*c[i]){

            LL tmp=b[i];b[i]=b[j];b[j]=tmp;

            tmp=c[j];c[j]=c[i];c[i]=tmp;

            tmp=a[i];a[i]=a[j];a[j]=tmp;

        }}

}

void dp(){

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

        for(int j=t;j>=c[i];j--)

          f[j]=max(f[j],f[j-c[i]]+a[i]-j*b[i]);

    }

    for(int i=1;i<=t;i++) f[0]=max(f[0],f[i]);

    printf("%d",f[0]);

}

int main()

{

    init();

    slove();

    dp();

    return 0;

}